Given a ~3 \times 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 \times 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/1GWzFwDaV1me5f6m9JFSoLX9LUcCF-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 1

2
*..
**.
*..
***
*..
..*

Example Output 1

1
3