10483번 - Shotcube 다국어

Namco Bandai’s video game ‘Tales of Graces’ introduces a puzzle minigame known as Shotcube. In this game, you have 9 cubes placed on a 7-by-7 square grid. The objective is to rearrange the cubes so that they all lie in a 3-by-3 square. In the video game, this 3-by-3 square must be in the exact center of the grid; for this problem, the 3-by-3 square may be anywhere on the grid.

The only way to rearrange the cubes is to "shoot" at them from the outside of the grid. If there is a cube adjacent to the edge of the grid, you may "shoot" it to push it in a straight line, in which it will keep moving until it hits another cube, at which point it stops. You may only shoot a cube if there is another cube in its path which stops it. If you shoot a cube in a direction such that one or more cubes are immediately behind it, all of those cubes will move in unison until the farthest cube hits another cube (after having travelled at least one grid square), at which point all of them stop.

Consider the grid below. The arrows mark the three legal shots; no other shots are legal, either because there is no cube adjacent to the edge of the grid, or because there is no cube present to stop the motion of the shot cubes. The three grids below that indicate the result of shooting the first row to the right, the first column down, and the fifth column down, respectively.

Figure 1: Illustration of legal shots and their outcomes.

Input begins with a line with a single integer T, 1 ≤ T ≤ 10000 denoting the number of test cases. Each test case consists of 7 lines, each with 7 characters, representing the 7-by-7 grid. Each character is either a "." (period) or an "X"; a "." indicates that that square is empty, while an "X" indicates that that square has a cube. Each test case is guaranteed to have exactly 9 cubes. Each pair of test cases is separated by a single blank line.

For each test case, print out the minimum number of shots needed to arrange the cubes into a 3-by-3 square anywhere on the grid, following the rules described above. If it is impossible to do so, print out the number "-1" instead.