Time Limit: 1000 mSec Memory Limit : 32768 KB

A substring of a string T=t_{1}…t_{n} is a string T’=t_{1+i}…t_{m+i}, where 0≤i and m+i≤n. A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix. For a string S, we define H(S) as harmonious substring function and the value of H(S) is the number of **different** substrings of S.

For example, the string “aab” only has five different substrings: “a”, “b”, “aa”, “ab”, “aab”, so the value of H(“aab”) is 5.
Now given n empty string s_{0},s_{1},…,s_{n-1}. Your task is to simulate the following two kinds of operations:

I i c: Push the character c in the front of the i-th string si (0 ≤ i < n, c is a lowercase letter);

S i j: Output the sum of the harmonious substring function from the i-th string s_{i} to the j-th string s_{j} (inclusive) (0 ≤ i ≤ j < n), that is

The first line of the input contains an integer T (T <= 20), indicating the number of cases. Each case begins with a line containing two integers n and q (1≤n≤50,000, 1≤q≤50,000), the number of strings and the number of operations. Each of the following q lines contains an operation that is said above.

For each test case, print a line containing the test case number (beginning with 1) on its own line, then the answer, one on each line. The output is generated by the operation “S i j”.

2
2 6
I 0 a
S 0 1
I 1 b
I 1 a
I 1 a
S 0 1
50000 1
S 0 50000

Case 1:
1
6
Case 2:
0