SP10454 GREENLAN - Greens Land

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.

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 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.

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