Limits 1s, 512 MB

Our beloved Robi Kaka has invented a cube. You have to solve only one side of this cube – a square of $N\times N$ cells. Every cell has $4$ colors – Red, Blue, Green, Yellow stripes drawn in clockwise direction one after another. There is also a white rotating button in the middle of each cell. Tapping it once rotates the cell $90°$ in clockwise direction.

We define the current state of a cell with its top color. Here are the four possible states of a cell, named after their top color $–$

You are given a jumbled square. Robi kaka calls it solved only if every adjacent cell of it shares same color.

Being the most talented bhatija, Robi kaka will ask you $Q$ queries. Every time Robi kaka will select cell $(i, j)$ and press the white button exactly once. Then Robi kaka asks you to find the minimum number of rotations (using the white button) needed to solve the square. Every rotation made by Robi kaka takes place.

Note that, to answer each query, you just take a look at the cube and answer the minimum number of rotation required. But you do not perform any operation on the cube.

Input

The first line contains an integer $T$ $\left(1 \leq T \leq 5\right)$, number of test cases.

For each test case the first line contains an integer $N$ $\left(1 \leq N \leq 500\right)$, length of the side of the square.

The following $N$ lines each contain a string of $N$ characters, denoting the initial square. The character in the $i$-th row and $j$-th column is one of '$\texttt{R}$', '$\texttt{Y}$', '$\texttt{G}$', '$\texttt{B}$' denoting the top color of the cell in the $i$-th row from top and $j$-th column from left of the square.

The next line will contain an integer $Q$ $\left(1 \leq Q \leq 10^5\right)$, the number of queries Robi Kaka will ask you.

The following $Q$ lines each contain $2$ numbers, $i$ and $j$ $\left(1 \leq i, j \leq N\right)$, meaning that Robi Kaka rotates the cell in $i$-th row from top and $j$-th column from left using the button in it.

Output

For each $Q$ query, print the minimum number of rotations needed to solve the square.

Sample

InputOutput
1
3
BGR
GGG
RGR
2
3 1
2 2
6
5

Submit

Login to submit.

Contributors

Statistics

85% Solution Ratio
akash740Earliest, Mar '21
steinumFastest, 0.0s
steinumLightest, 5.5 kB
Zobayer_AbedinShortest, 1349B
Toph uses cookies. By continuing you agree to our Cookie Policy.