D. Double String
time limit per test
2 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

SoCCat has a string $$$S$$$ consisting of lowercase English letters a to z. For their Final Year Project, SoCCat is interested in the so-called double string.

Formally, a string $$$T$$$ is a double string if and only if:

  • $$$T$$$ has even length.
  • The first half of $$$T$$$ is equal to the second half of $$$T$$$. In other words, $$$T_i = T_{i + \frac{|T|}{2}}$$$ for all $$$1 \leq i \leq \frac{|T|}{2}$$$.

Help SoCCat count the number of pairs of indices $$$(i, j)$$$ such that $$$1 \leq i \lt j \leq |S|$$$ and the substring $$$S[i, j] = S_i S_{i+1} \dots S_{j}$$$ is a double string!

Input

The input contains a string $$$S$$$ ($$$1 \leq |S| \leq 200\,000$$$) consisting of lowercase English letters a to z.

Output

Output a single integer denoting the number of pairs of indices $$$(i, j)$$$ such that $$$1 \leq i \lt j \leq |S|$$$ and the substring $$$S[i, j]$$$ is a double string.

Examples
Input
mississippi
Output
5
Input
aaaaa
Output
6
Input
soc
Output
0
Note

In the first sample, $$$S = \texttt{mississippi}$$$. All the substrings that are double strings are:

  • $$$\texttt{ississ}$$$, with $$$i = 2$$$ and $$$j = 7$$$.
  • $$$\texttt{ssissi}$$$, with $$$i = 3$$$ and $$$j = 8$$$.
  • $$$\texttt{ss}$$$, with $$$i = 3$$$ and $$$j = 4$$$.
  • $$$\texttt{ss}$$$, with $$$i = 6$$$ and $$$j = 7$$$.
  • $$$\texttt{pp}$$$, with $$$i = 9$$$ and $$$j = 10$$$.

Thus, the answer is $$$5$$$.

In the second sample, $$$S = \texttt{aaaaa}$$$. All pairs of indices $$$(i, j)$$$ such that $$$j-i+1$$$ is even are double strings. Thus, the answer is $$$6$$$.

In the third sample, $$$S = \texttt{soc}$$$. There are no double strings in this case, so the answer is $$$0$$$.