D. Colored Portalstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere 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$$$.InputThe 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$$$. OutputFor each query, print a single integer — the minimum cost to move from city $$$x$$$ to city $$$y$$$ (or $$$-1$$$ if it is impossible).ExampleInput24 5BR BR GY GR1 23 14 41 44 22 1BG RY1 2Output1 4 0 3 2 -1