Cho ma trận kích thước ~n \times n~, mỗi ô của ma trận chứa ký tự Hoa thuộc bảng chữ cái. Ví dụ:

$$\displaystyle \begin{bmatrix} A & B & C & D\\ B & X & Z & X\\ C & D & X & B\\ W & C & B & A \end{bmatrix} $$

Một đường đi xuất phát từ góc trái trên đến gốc phải dưới, mỗi bước được phép đi qua phải hoặc đi xuống dưới, như vậy mỗi đường đi sẽ là một xâu các ký tự (đi qua ô nào thì gắn ký tự của ô vào xâu).

Hãy lập trình đếm số xâu Palindrome theo các cách đi khác nhau, chú ý một xâu Palindrome được tạo thành bằng nhiều cách đi chỉ tính một lần. Ví dụ ma trận trên cho xâu Palindrome ABXZXBA bằng nhiều cách khác nhau.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ là kích thước ma trận thỏa ~2 \le n \le 18~.

~n~ dòng tiếp theo, mỗi dòng chứa ~n~ ký tự alphabet in hoa.

Output

In ra số xâu Palindrome cần tìm.

Samples

Sample Input

4
ABCD
BXZX
CDXB
WCBA

Sample Output

4

Note

Có 4 xâu Palindrome khác nhau là ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.