SOLVE
LATER
This Holi, Monk wants to distribute sweets to the houses of his colony. The houses of the colony are present in a circular order (i.e. house 1 and house N are adjacent to each other).
Kids love to play with colors but currently there is a supply of only 2 types of colors (Red represented by R and Green represented by G). Due to festive season each of the kids have colored their houses with either green or red color.
Monk is given a task of distributing sweets Q number of times. Every time he is asked to travel from \(x^{th}\) house to \(y^{th}\) house to distribute the sweets.
The distribution strategy is that he starts from \(x^{th}\) house and he has to give 1 sweet to a house only when he travels from green house to a red house or vice-versa. Monk can travel from \(x^{th}\) house to \(y^{th}\) house either in clockwise direction or in anti-clockwise direction.
Monk wants your help to find the minimum number of sweets he should carry to complete his journey.
Input Format
First line contains an integer T denoting the number of test cases.
Each test case contains an integer N and Q.
Next line contains a string S (representing the house colors) of length N.
Then Q lines follow, each containing 2 integers x and y.
Output Format
For each test case print Q lines containing the minimum number of sweets he must carry with himself.
Input Constraints
\(1 \le T \le 100 \)
\(1 \le N,Q \le 1000 \)
\(1 \le x,y \le N \)
S consists of only letters 'G' and 'R'
Case 1:
For 1st query, if we travel in the direction 1->2->3->4->5, we need only one sweet . If we travel in the direction 1->5, we need only one sweet. So he has to carry only 1 sweet.
For 2nd query, if we travel in the direction 3->4->5->1->2, we need two sweets. If we travel in the direction 3->2, we need no sweets. So he has to carry 0 sweets.
Case 2:
For 1st query house, 2 and 5 can be travelled using path 2->1->5 without any change of colors so he has to carry 0 sweets.
For 2nd query house 3 and 1 can be travelled using path 3->2->1 with a change of color so he has to carry 1 sweet.