本题没有可用的提交语言。

Mr. Green has a large portion of land divided into square units that are either field or lake areas.
He wants to fence a rectangular portion of his lands to use for livestock.
The lake areas have a very soft soil and any fence built near those areas have a chance to fall (and
then the animals could escape), so no fence should be built near a lake area.

Mr. Green wants to know of how many ways he can fence a rectangular area of his lands without
any portion of the fence having a common border with a lake area.
In the example above, for a 3x3 land with a lake area in the center, we have 5 possibilities of fence.

Input

On the first line a positive integer: the number of test cases, at most 100. After that per test case:
One line with a integer N (1 ≤ N ≤ 300): the size of the land (N xN ).
N lines, each with N characters. Each character is either ‘.’ or ‘X’. The j − th character on the
i − th line is a ‘X’ if position (i, j) is a lake area, and ‘.’ if it is a field area.

Output

For each test case output a line with the number of different valid ways wich Mr. Green can fence his
lands.

Example

Input:
4
3
...
.X.
...
3
X..
...
X..
6
......
......
......
......
......
......
5
.....
....X
.X...
.....
...XX

Output:
5
8
441
23