EIU Programming Practices and Exams

Given a 3 x 3 square with some white and 1 black squares. When clicking on a cell, that cell and the cells with the same edge will change color from white to black and vice versa. Given a 3 x 3 square, ask for the minimum number of taps to turn the all-white square into the given square.

Visualization: https://drive.google.com/file/d/1G_Wz_FwDaV1me5f6m9JFSoLX9LUcCF-U/view?usp=drive_link

Input

The first line is the number of testcases

Each testcase consists of 3 lines, each line is 3 characters representing the color of 3 cells in that line where '*' is black, '.' is white

Output

The minimum number of steps of each testcase on 1 line

Example

Input:
2
*..
**.
*..
***
*..
..*

Output:
1
3