Nhật rất thích những thứ liên quan đến tam giác, và đặc biệt hơn là việc đếm số tam giác. Một hôm nọ, anh ấy có một bảng vuông \(n \times n\) chỉ chứa các ký tự . và #. Các hình tam giác có dạng:

Một cách dễ hiểu hơn, tam giác bậc \(k\) bao gồm \(k\) hàng cho mọi số nguyên dương \(k\). Hàng thứ \(i\) trong \(k\) hàng chứa \(2i - 1\) ký tự # (tính từ trên xuống dưới) (\(i = 1 \dots k\)). Các hàng được xếp chồng lên nhau theo căn lề giữa để chúng đối xứng với nhau qua trục đi qua trung điểm của mỗi hàng.

Nhật đang khá là bối rối trong việc đếm số lượng các tam giác thỏa mãn trên ma trận vì kết quả của chúng có thể rất là lớn. Các bạn hãy giúp anh ấy đếm tất cả các tam giác nhé!

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) là kích thước của ma trận.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo là dãy gồm \(N\) ký tự, mỗi ký tự chứa một trong 2 ký tự . hoặc #.

Output

• Xuất ra một số nguyên dương là số tam giác cần tìm.

Example

5
.....
.###.
.###.
#####
.....

16

3
###
###
###

11

Constraints

• \(N \le 2000\).