Replication

Một robot tự nhân bản được thả xuống lưới $N\times N$ gồm các ô đá và ô trống. Ban đầu chỉ có đúng một robot, đứng tại một trong các ô được đánh dấu S.

Mỗi giờ, toàn bộ robot đang có (bản gốc lẫn các bản sao) cùng di chuyển sang ô kề theo cùng một hướng trong 4 hướng: lên, xuống, trái, phải. Đàn robot không được thực hiện bước đi khiến một robot nào đó bước vào ô đá.

Cứ sau mỗi $D$ giờ, tức tại các thời điểm $D,2D,3D,\dots$, mỗi robot sinh thêm một bản sao tại cả 4 ô kề của nó, bản thân robot vẫn đứng yên tại chỗ. Việc nhân bản là bắt buộc và xảy ra sau bước đi của giờ đó. Vì vậy sau $t$ giờ, đàn robot phủ đúng hình thoi gồm mọi ô có khoảng cách Manhattan không quá $\lfloor t/D\rfloor$ tới ô trung tâm.

Nếu một bản sao sinh ra rơi vào ô đá thì cả đàn robot tắt ngay lập tức và không hoạt động trở lại. Những ô mà đàn robot đã chiếm giữ trước lần nhân bản hỏng đó vẫn được tính là đã từng chứa robot.

Xét mọi cách chọn ô xuất phát S và mọi cách di chuyển, hãy đếm số ô trống có thể chứa robot (bản gốc hoặc bản sao) tại một thời điểm nào đó.

Dữ liệu vào

• Dòng 1: hai số nguyên $N$ và $D$
• $N$ dòng tiếp theo: mỗi dòng $N$ ký tự mô tả lưới
  • . hoặc S là ô trống (S là một vị trí xuất phát có thể)
  • # là ô đá

Dữ liệu ra

Một số nguyên duy nhất: số ô trống có thể chứa robot.

Ràng buộc

• $3\le N\le 1000$
• $1\le D\le {10}^9$
• Mọi ô nằm trên biên của lưới đều là đá
• Có ít nhất một ô S

Ví dụ