Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

J. String Split
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Brook is trying to write a beautiful, soulful new song using a long string of lyrics $$$s$$$.

Robin reads over his sheet music and suggests cutting the lyric string into three specific non-empty parts A, B, and C such that $$$A + B + C = s$$$ to create an echoing effect so that:

  • A is a prefix of C;
  • B is a suffix of C.

A and B can overlap inside C. Different cuts are counted as completely different musical arrangements. Help Robin find the number of ways to cut the string so Brook can sing his song.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.

Each test case has one line with a string $$$s$$$ ($$$3 \le |s| \le 2 \times 10^{5}$$$). It has lowercase letters.

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

Output

For each test case, output one integer — the number of ways to cut the string.

Example
Input
3
aaaaaa
aaaa
abc
Output
4
1
0
Note

For $$$s = \texttt{aaaaaa}$$$, the valid splits are:

  • $$$A = \texttt{a}$$$, $$$B = \texttt{a}$$$, $$$C = \texttt{aaaa}$$$;
  • $$$A = \texttt{a}$$$, $$$B = \texttt{aa}$$$, $$$C = \texttt{aaa}$$$;
  • $$$A = \texttt{aa}$$$, $$$B = \texttt{a}$$$, $$$C = \texttt{aaa}$$$;
  • $$$A = \texttt{aa}$$$, $$$B = \texttt{aa}$$$, $$$C = \texttt{aa}$$$.
In the last split, the matching prefix and suffix inside $$$C$$$ are the same two characters.

For $$$s = \texttt{aaaa}$$$, the valid split is $$$A = \texttt{a}$$$, $$$B = \texttt{a}$$$, and $$$C = \texttt{aa}$$$.

For $$$s = \texttt{abc}$$$, no split satisfies both conditions.