If a string can be split into the form $AABB$, where $A$ and $B$ are any non-empty strings, we call this split of the string "excellent".

For example, for the string aabaabaa, if we let $A = \text{aab}$, $B = \text{a}$, we have found one way to split this string into $AABB$.

A string may have no excellent splits, or it may have more than one. For example, if we let $A = \text{a}$, $B = \text{baa}$, we can also represent the above string as $AABB$; however, the string abaabaa has no excellent splits.

Given a string $S$ of length $n$, we need to find the total number of excellent splits among all substrings of $S$. Here, a substring refers to a contiguous segment of the string.

The following points should be noted:

1. Identical substrings appearing at different positions are considered different substrings, and their excellent splits will all be counted towards the answer.
2. In a split, it is allowed for $A = B$. For example, cccc has a split $A = B = \text{c}$.
3. The string itself is also one of its substrings.

Input Format

The input file is excellent.in.

Each input file contains multiple test cases. The first line of the input file contains a single integer $T$, representing the number of test cases. It is guaranteed that $1 \le T \le 10$.

Each of the next $T$ lines contains a string $S$ consisting only of lowercase English letters, as described in the problem description.

Output Format

The output file is excellent.out.

Output $T$ lines, each containing an integer, representing the total number of excellent splits among all substrings of the string $S$.

Examples

Input 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Output 1

3
5
4
7

Note

We use $S[i, j]$ to denote the substring of $S$ from the $i$-th character to the $j$-th character (1-indexed).

In the first test case, there are 3 substrings that have excellent splits: $S[1, 4] = \text{aabb}$, with an excellent split $A = \text{a}, B = \text{b}$; $S[3, 6] = \text{bbbb}$, with an excellent split $A = \text{b}, B = \text{b}$; $S[1, 6] = \text{aabbbb}$, with an excellent split $A = \text{a}, B = \text{bb}$. The remaining substrings do not have excellent splits, so the answer for the first test case is 3.

In the second test case, there are two types, totaling 4 substrings that have excellent splits: For the substrings $S[1, 4] = S[2, 5] = S[3, 6] = \text{cccc}$, they have the same excellent split, $A = \text{c}, B = \text{c}$, but since these substrings are at different positions, they must be counted 3 times; For the substring $S[1, 6] = \text{cccccc}$, it has 2 types of excellent splits: $A = \text{c}, B = \text{cc}$ and $A = \text{cc}, B = \text{c}$. These are different splits of the same substring, and both must be counted. So the answer for the second test case is $3 + 2 = 5$.

In the third test case, $S[1, 8]$ and $S[4, 11]$ each have 2 types of excellent splits, where $S[1, 8]$ is the example from the problem description, so the answer is $2 + 2 = 4$.

In the fourth test case, $S[1, 4], S[6, 11], S[7, 12], S[2, 11], S[1, 8]$ each have 1 type of excellent split, and $S[3, 14]$ has 2 types of excellent splits, so the answer is $5 + 2 = 7$.

Subtasks

For all test cases, it is guaranteed that $1 \le T \le 10$. The following constraints apply to each individual test case. Let $n$ be the length of the string $S$.