403235: GYM101086 G Paradise City

G. Paradise Citytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Noura has been looking for a restaurant to host the SCPC2015 celebration in Lattakia, she decided that the best method to pick a restaurant is according to the number of contestants that are living near it. Given a grid representing the map of Lattakia, each 3x3 cells represent a district, each district will consist of 3x3 areas. The center of each district is a restaurant (X), other cells can be:

  ‘.’ denotes an empty block.
  ‘*’ denotes a block full of people (4 persons)

Help Noura decide which restaurant to choose by finding the maximum number of students living in a district.Input

The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.

The first line of each test case contains an integer N (1 ≤ N ≤ 100), the number of districts. Then follows three lines, each consists of 3 × N characters, representing the map of the city of N districts.

Output

For each test case, print the maximum number of students living in a district on a single line.

ExamplesInput

3
3
***...***
.X.*X*.X.
***...***
2
*.*.*.
.X..X*
*.*.*.
3
.*...****
*X**X**X*
...*..*.*

Output

24
16
28

Note

Warning: large Input/Output data, be careful with certain languages.