One day, you found a magic box on the road with its manual.
This box is an nxnxn cube, and you can fill one energy crystal in each 1x1x1 cell. There are two types of energy crystal: positive and negative.
When two adjacent cells(shared by a face) are filled by different types of crystals, they will produce one unit of energy! MAGIC!
Now, some cells of the box have been filled, while others are empty. You want to know the maximum energy it can produce, if you fill the remaining cells in an optimal way.
The first line of the input will be an integer T (1<=T<=200), denoting the number of test cases.
For each test case, the first line contains an integer n (1<=n<=10), followed by n2 lines, each line contains n characters describe the magic box, `P' for positive, `N' for negative, and `?' for empty.
Output the answer in one line per test case.