The LCP (Longest Common Prefix) of two strings A[1..la] and B[1..lb] is defined as follows:

LCP(A[1..la], B[1..lb]) = max{L | L ≤ la && L ≤ lb && A[1..L] == B[1..L]}

Given an original string and several operations, you should write a program to process all the operations.

Input

The first line will be number of test cases T.
The first line of each test case is a string S with length L (1 ≤ L ≤ 100000).
The second line contains an integer Q(1 ≤ Q ≤ 150000), representing the number of operations.

Each of the following Q lines represents an operation:
Q i j: print LCP(S[i..L], S[j..L])
R i char: replace the i-th character of S with char
I i char: insert character char after the i-th character of S

Output

For each "Q i j" operation, print the answer.

Example

Input:
1
madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

Output:
5
1
0
2
1