403233: GYM101086 E Going in Circles

E. Going in Circlestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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| ≤ 10⁴).

|S| represents the length of the string S.

Output

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

ExamplesInput

3
AbB
AcMsCpC
syria

Output

8
36
100

Note

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