В результате просмотра слишком большого количества видео по технике "сделай сам" в сети, фермер Джон случайно выпустил самовоспроизводящегося робота на своей ферме!

Ферма представляется сеткой n × n, где каждая ячейка либо пуста, либо заполнена камнем, а все граничные квадраты заполнены камнем. Некоторые ячейки, не являющиеся каменными, обозначены как возможные стартовые места для робота.

Фермер Джон сначала ставит робота на одну из возможных стартовых позиций. В каждый последующий час все копии робота движутся одной скоординированной массой в одном направлении: на север, юг, восток или запад. Через каждые d часов каждая копия робота реплицируется - робот в ячейке (x, y) создает новые копии в ячейках (x + 1, y), (x − 1 , y), (x, y + 1) и (x, y − 1); исходный робот остается в (x, y). Со временем несколько роботов могут занять одну и ту же ячейку.

Если перемещение или репликация заставит любого из роботов переместиться в скалу, то все роботы немедленно отключатся. Обратите внимание, что роботы должны в конечном итоге выключиться из-за того, что граница фермы скалистая.

Помогите коровам вычислить количество пустых квадратов, которые потенциально могут в какой-то момент времени содержать робота.

Входные данные

Первая строка содержит два целых числа n (3 ≤ n ≤ 1000) и d (1 ≤ d ≤ 109). Каждая из следующих n строк ввода содержит n символов. Каждый символ может быть одним из символов '.', 'S' или '#'. '.' и 'S' обозначают пустые ячейки, 'S' обозначает возможную начальную позицию для робота. '#' обозначает камень.

Все символы в первой и последней строке, а также в первом и последнем столбце равны '#'.

Выходные данные

Выведите одно целое число - количество ячеек, которые в какой-то момент времени могут содержать робота.

Пример

На следующих диаграммах x обозначают роботов. Места, которые могут быть заняты роботами:

##########
#xxx.....#
#xxxx....#
#xxx.....#
##########
#xx..xxx.#
##########
##########
##########
##########

Рассмотрим одну из возможных последовательностей событий:

• ФД помещает робота в крайнее левое начальное положение.
• Робот перемещается на одну единицу вправо.
• Робот реплицирует.
• Все роботы перемещаются на одну единицу вправо.
• Вторая репликация приведет к тому, что копия робота переместится в скалу, поэтому процесс завершается.

##########    ##########    ##########    ##########
#........#    #........#    #.x......#    #..x.....#
#x.......#    #.x......#    #xxx.....#    #.xxx....#
#........#    #........#    #.x......#    #..x.....#
########## -> ########## -> ########## -> ##########
#........#    #........#    #........#    #........#
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########