E. Going in Circles
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

During the SCPC2015 celebration, and as Noura likes to keep everyone entertained, she wanted to play a game with the students and volunteers. She asked them to stand in a circle in order to assign them into 2 groups.

The rules for forming the two groups are:

  • Every student must be a member of exactly one of the two groups.
  • A volunteer can be a member of at most one group.
  • Students from the same university should be in the same group (even if that means the inequality in size of the two groups).
  • The members of each group should form a non-empty contiguous part of the circle.
  • Groups should be formed without changing the order of the students and volunteers in the circle.
The university of a student will be represented by uppercase English letters (A-Z), and the university of a volunteer will be represented by lowercase English letters (a-z).

Given a string that you should treat as a circle (which means that the last letter is a neighbor to the first one), calculate the number of ways to choose two ordered, non - overlapping substrings that represent the two groups and satisfy the given rules.

Input

The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.

Each test case will consist of a single line that contains a string S (2 ≤ |S| ≤ 104).

|S| represents the length of the string S.

Output

For each test case, print the number of ways on a single line.

Examples
Input
3
AbB
AcMsCpC
syria
Output
8
36
100
Note

Warning: large Input/Output data, be careful with certain languages.