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'