暂无测试数据。

在网上观看太多机械 DIY 视频的后果就是，Farmer John 偶然在他的农场上制造了一个可以自我复制的机器人！ 农场可以用一个 N×N 的方阵表示（$3 \le N \le 1000$），其中每个方格是空的或有岩石，并且所有边界上的方格均有岩石。某些没有岩石的方格被指定为机器人可能的起始位置。

Farmer John 初始将机器人放置在可能的起始位置之一。在之后的每一个小时，机器人的所有副本会沿着相同的方向移动一格，向北、向南、向东或向西。每 D 个小时（$1 \le D \le 10^9$）之后，机器人的每个副本会进行自我复制——在方格 (x,y) 进行自我复制的机器人会在方格 (x+1,y)、(x−1,y)、(x,y+1) 以及 (x,y−1) 产生机器人的新的副本；原本的机器人仍然位于 (x,y)。一段时间过后，同一方格内可能会有多个机器人。

如果移动或复制会使得任何一个机器人撞到岩石，那么所有的机器人均立刻停止行动。注意这意味着所有机器人最终必然会停下，由于农场的边界都是岩石。

请帮助奶牛们求出可能在某个时刻含有机器人的空的方格数量。

输入格式（从终端/标准输入读入）

输入的第一行包含两个空格分隔的整数 N 和 D。以下 N 行每行包含 N 个字符。每个字符均为 '.'、'S' 和 '#' 之一。'.' 和 'S' 均表示空的方格，且 'S' 表示一个可能的机器人起始位置。'#' 表示一块岩石。

所有第一行、最后一行、第一列、最后一列的字符均为 '#'。

输出格式（输出至终端/标准输出）

输出一个整数，表示可能在某个时刻含有机器人的方格数量。

测试点性质

• 测试点 4-5 满足 $D=10^9$。
• 测试点 6-8 满足 D=1。
• 测试点 9-12 满足 N≤100。
• 测试点 13-20 没有额外限制。

10 1
##########
#........#
#S.......#
#........#
##########
#S....S..#
##########
##########
##########
##########

15

10 2
##########
#.#......#
#.#......#
#S.......#
#.#......#
#.#......#
##########
##########
##########
##########

28

10 2
##########
#.S#.....#
#..#.....#
#S.......#
#..#.....#
#..#.....#
##########
##########
##########
##########

10