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 x N). 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 which Mr. Green can fence his lands.

Example

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

Output:
5
8
441
23