Aether is travelling across Teyvat, which can be represented by a ~N~ by ~N~ grid, where each cell ~A_{i,j}~ is either empty . or contains a teleporter x. Due to terrain and weather reasons, he can only move down and to the right. Formally, if he is at the cell ~(r, c)~, he can go to ~(r + 1, c)~ if ~r \neq N~, and he can go to ~(r, c + 1)~ if ~c \neq N~.

Whenever he is at a cell containing a teleporter, he can choose to teleport to any other cell containing a teleporter. Each teleporter can be used an unlimited number of times.

Since Aether likes exploring new areas, he would like to know, what is the maximum number of unique cells ~(r, c)~ that he can visit if he starts at the top-leftmost cell ~(1, 1)~?

Constraints

~1 \le N \le 2000~

~A_{i,j} \in \{~.~,~x~\}~

Subtask 1 [5%]

There are no teleporters. Formally, ~A_{i,j} \neq~ x.

Subtask 2 [45%]

~1 \le N \le 100~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line of input contains ~1~ integer, ~N~, representing the dimensions of the grid.

The next ~N~ lines of input each contain ~N~ characters, ~A_{i,j}~, representing the cells in each row.

Output Specification

Output ~1~ integer, the maximum number of unique cells that Aether can visit.

Sample Input 1

3
...
..x
.x.

Sample Output 1

6

Explanation for Sample 1

The following path visits ~6~ unique cells:

• Start at ~(1, 1)~
• Go to ~(1, 2)~
• Go to ~(1, 3)~
• Go to ~(2, 3)~
• Teleport to ~(3, 2)~
• Go to ~(3, 3)~

It can be proven that this is the maximum number of unique cells Aether can visit.

Sample Input 2

5
x....
.x...
...x.
.....
.x..x

Sample Output 2

25