Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

Given a string containing 'a' to 'z' with length N(1<=N<=100000)

You have two operations:

Q L R : output the length of the longest consecutive non-decreasing subsequence

C L R P : replace each letter from L to R by letter P('a'<=P<='z')

in which,1<=L,R<=N.what's more,maybe you should know the fact 'a'<'b'<'c'<...<'z' .

SA10010044 considers it an easy task ,isn't it ?

Input

T in the first line,indicating the case number(T<=10). Each case starts with a string(the length of it will be no more than 100000) The next line contains a number QQ,representing the operation number.(1<=QQ<=100000). Then the next QQ lines,each line has an operation: Q L R C L R P as described above.Notice : L may be larger than R.

Output

For each Q,output the answer.

Sample Input

1
abcdef
5
Q 1 6
C 3 4 b
Q 1 3
C 4 5 c
Q 2 5


Sample Output

6
3
4


from friend