E. Tung Tung String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
What if instead of Triple T it was Double T, and instead of Sahur it was a String?
— Mark Twain

Oh no! Tung Tung Sahur is now Tung Tung String and his letters are all messed up! He needs your help ASAP.

Given a string $$$s$$$, output the minimum number of adjacent swaps required to make $$$s$$$ of the form $$$t + t$$$ for some string $$$t$$$. This will bring back Tung Tung String back to his original form!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). The description of each test case follows.

Each test case contains a single line with a string $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$). Each string consists of lowercase Latin letters.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one integer — the minimum number of adjacent swaps required. The input guarantees that the goal can be achieved within a finite number of swaps.

Example
Input
3
aabb
abab
aaaabbbb
Output
1
0
4
Note

In the first test case, we can swap the second and third characters to form "abab".

In the second test case, no swaps are required.

In the third test case, we can use four swaps to form "aabbaabb".