Replication

Một robot tự nhân bản được đặt trên lưới $N\times N$ chứa đá và ô trống. Robot bắt đầu tại các ô được đánh dấu 'S'. Mỗi giờ, robot có thể di chuyển theo 4 hướng (tất cả bản sao cùng di chuyển). Cứ mỗi $D$ giờ, mỗi robot tạo ra bản sao tại 4 ô kề (bản gốc vẫn ở vị trí cũ). Nếu robot hoặc bản sao đi vào ô có đá, tất cả đều tắt.

Đếm số ô trống có thể chứa robot 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' = ô trống (S = vị trí bắt đầu)
  • '#' = đá
  • Tất cả ô biên là đá

Dữ liệu ra

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

Ràng buộc

• $3\le N\le 1000$
• $1\le D\le {10}^9$

Ví dụ