Shotcube

No attempts yetTime limit10sMemory limit256 MB

Problem

The video game Tales of Graces has a puzzle minigame called Shotcube. Nine cubes sit on a 7×77 \times 7 grid, and the goal is to gather all of them into a 3×33 \times 3 square. The original game requires that square to be at the exact center of the grid. In this problem it may be anywhere on the grid.

The only way to move the cubes is to shoot at them from outside the grid. Pick one row or one column and shoot inward from its outer side. The shot is allowed only if the cell of that line touching the edge of the grid holds a cube. The unbroken run of cubes that starts at that cell and continues in the direction of the shot slides as one piece. It keeps going until the leading cube is blocked by another cube, and then the whole run stops with the leading cube on the cell just before the blocker. If no cube in that direction can stop the run, you may not shoot that way. A shot always moves the run by at least one cell.

Find the smallest number of shots that gathers the nine cubes into a 3×33 \times 3 square.

Input

The first line holds the number of test cases TT (1T100001 \le T \le 10000).

Each test case consists of 7 lines of 7 characters each. Every character is either . or X, where . is an empty cell and X is a cell holding a cube. Every test case has exactly 9 cubes. A single blank line separates one test case from the next.

Output

For each test case, print on its own line the smallest number of shots that gathers the nine cubes into a 3×33 \times 3 square. If no sequence of shots does that, print -1 instead.