Little Cyan Fish likes string theory very much. Today, Little Cyan Fish invites you to study human nicknames with him.

In Little Cyan Fish's universe, human nicknames can all be represented as a string containing only lowercase Latin letters (a to z). For example, "qingyu" and "xiuga" are human nicknames, but "Abacde" is not a human nickname.

Little Cyan Fish considers a name $s$ to be Lyndon if and only if for each proper suffix* $t$ of $s$, the lexicographical order of $s$ is strictly smaller than $t$. For example, "abacde" is a Lyndon string, but "qingyu" is not a Lyndon string (because the original string is not lexicographically smaller than the proper suffix "ingyu").

Now, Little Cyan Fish gives you a human nickname $s$, and you need to calculate how many different pairs of $(l, r)$ with $1 \le l \le r \le |s|$ exist such that $s[l \dots r]$ is Lyndon.

* A proper suffix is a non-empty suffix that is not equal to the original string. For example, "qqoj" has $3$ proper suffixes, which are "j", "oj", and "qoj".

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T$), indicating the number of test cases.

For each test case, the input contains a single line with a string $s$ ($1 \le |s| \le 2 \times 10^5$), indicating the human nickname.

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

Output

For each test case, output a single line containing one integer, indicating the answer.

Example

Input 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Output 1

3
9
27
16
58
32