D. Colored Portals
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ cities located on a straight line. The cities are numbered from $$$1$$$ to $$$n$$$.

Portals are used to move between cities. There are $$$4$$$ colors of portals: blue, green, red, and yellow. Each city has portals of two different colors. You can move from city $$$i$$$ to city $$$j$$$ if they have portals of the same color (for example, you can move between a "blue-red" city and a "blue-green" city). This movement costs $$$|i-j|$$$ coins.

Your task is to answer $$$q$$$ independent queries: calculate the minimum cost to move from city $$$x$$$ to city $$$y$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of cities and the number of queries, respectively.

The second line contains $$$n$$$ strings of the following types: BG, BR, BY, GR, GY, or RY; the $$$i$$$-th of them describes the portals located in the $$$i$$$-th city; the symbol B indicates that there is a blue portal in the city, G — green, R — red, and Y — yellow.

The $$$j$$$-th of the next $$$q$$$ lines contains two integers $$$x_j$$$ and $$$y_j$$$ ($$$1 \le x_j, y_j \le n$$$) — the description of the $$$j$$$-th query.

Additional constraints on the input:

  • the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$;
  • the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Output

For each query, print a single integer — the minimum cost to move from city $$$x$$$ to city $$$y$$$ (or $$$-1$$$ if it is impossible).

Example
Input
2
4 5
BR BR GY GR
1 2
3 1
4 4
1 4
4 2
2 1
BG RY
1 2
Output
1
4
0
3
2
-1