One day, Umaru was enjoying Coke and potato chips as usual. Suddenly, an intellectual problem appeared on the television and the person who asked the problem first and correctly will get the latest《Jump》. Umaru really wants to get the 《Jump》so she told her brother the problem and begged him to help her. But her brother didn’t know how to do it, so he told you the problem and asked you for help.
There was a $N×N$ matrix and each grid is black or white. The host reversed the color of the grid or reversed the color of the whole columns. Then the problem was how many white and black connected components. (If two grids have a common edge, we think they are connected.) To increase difficulty, the grid $(i,1)$ and the grid $(i,N)$ are connected. $(1\leq i \leq N)$.

The first line of the input contains an integer $T (1 \le T \le 15)$, denoting the number of test cases.
In each test case, the first line contains one integer N, which means the size of the matrix.
In the next $N$ lines, each line contains $N$ integers(0 or 1) means the color of each color. 1 represents black and 0 represents white.
Then the integer $Q$ represents the number of reversals that the host does. Each line of the $Q$ lines contains several numbers. If the first number is 1, the next one number $y$ is the columns of the reversal. If the first number is 2, the next two numbers $x$ and $y$ represents the position of the reversal.
$2 \leq N \leq 200$
$1 \leq Q \leq 20000$

The output contains $Q$ lines. The $i$-th line contains two integers which represent the number of the white and black connected components after the first $i$ operations