Coach Pang likes strings. He is also interested in algorithms. A few days ago he discovered for himself a very nice problem: You are given an XY-string S. You need to count the number of substrings of S, which have an equal number of X's and Y's.

Do you know how to solve it? Good. Coach Pang will make the problem a little bit more difficult for you.

You are given an XYZ-string S. You need to count the number of substrings of S, which have an equal number of X's, Y's and Z's.

A string is called XY-string if it doesn't contain any symbols except 'X' or 'Y'. A string is called XYZ-string if it doesn't contain any symbols except 'X', 'Y' or 'Z'.

A bit more difficulty is added to the Question characters 'X' ,'Y' and 'Z' will change for each test case.

Input

The first line of the input contains T (number of test cases).For each test case there will be two lines.First contains a string of length three ("XYZ") (only upper case letters) representing 'X', 'y' and 'Z' respectively. Second line contains the XYZ-String S.

Output

For each test case your output should contain the only integer, denoting the number of substrings of S, which have an equal number of X's, Y's and Z's.

Constraints

1 ≤ T ≤ 6
1 ≤ |S| ≤ 1000000; where |S| denotes the length of the given XYZ-string.

Sum of all the strings S in the test file will not exceed 5000000.

Example

Input:
2
XYZ
XYZXYZ
ABC
ABACABA

Output:
5
2

Explanation

In the first example you should count S[1..3] = "XYZ" , S[2..4] = "YZX", S[3..5] = "ZXY" , S[4..6] = "XYZ" and S[1..6] = "XYZXYZ".

Similarly in the second example you should count S[2..4] = "BAC" and S[4..6] = "CAB".