The Safe

The front of a safe is an $N \times N$ grid with one knob in every cell. A knob is either horizontal (-) or vertical (|), and turning it switches it to the other state.

The knobs are numbered 1 to $N^2$, left to right along the top row and then down row by row, as in the left figure below. At the start every knob is horizontal, as in the right figure. The door opens only while every knob is horizontal.

Starting from the open door, you lock the safe like this. Pick one knob and turn it, so a horizontal knob becomes vertical and a vertical knob becomes horizontal. The important part is that every knob sharing a row or a column with the chosen knob also changes direction.

For example, turning knob 6 in the initial state gives the left figure below, and turning knob 11 from there gives the right figure.

You are given the state of a locked safe. Find the smallest number of turns that makes every knob horizontal again and opens the door.

Input arrives on standard input. The first line holds the number of test cases $T$ ($1 \le T \le 20$). Each test case starts with a line holding the safe size $N$, an even number between 2 and 20. The next $N$ lines describe the safe, $N$ characters per line separated by single spaces. Each character is H or V, where H is a horizontal knob and V is a vertical knob.

Write to standard output. For each test case print the minimum number of turns needed to open the safe, one per line.