H. 我爱XTU
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定长度为 n 的，由 XTU 三个字符构成的字符串 S，现请你输出 S 中满足三种字符数量相同的子串的数量

Input

第一行一个整数 T(1 ≤ T ≤ 100)，表示数据组数

接下来 T 行，每行为一个仅由字符 X、T、U 组成的字符串 S

数据保证字符串长度 len(S) ≤ 104

Output

输出 T 行，每行一个整数，表示合法子串的数量

Example
Input
2
XXTUUTXTU
UTUXXTTUXUXX
Output
6
8