XYZSTR - XYZ-Strings

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".


Added by:Aditya Dixit
Date:2014-09-23
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PS PROLOG PYTHON PYPY PYPY3 PYTHON3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.