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.

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$.