给定一个由小写字母组成的字符串 $s$。对于该字符串，我们记其长度为 $|s|$，记其反串为 $s^R$（即将 $s$ 左右颠倒后得到的字符串）。同时，我们用 $\operatorname{prefix}(s, i)$ 表示由 $s$ 的前 $i$ 个字符组成的子串，用 $\operatorname{suffix}(s, i)$ 表示由 $s$ 的后 $i$ 个字符组成的子串。

在此基础上，我们定义字符串 $s$ 的 $\operatorname{Porder}$ 值为满足以下条件的最大整数 $i$： $$\operatorname{prefix}(s, i) = (\operatorname{suffix}(s, i))^R$$其中 $0 \le i \le |s|$。特别地，若不存在正整数满足上述条件，则 $\operatorname{Porder}$ 值为 $0$。

字符串 $s$ 的子串定义为其从第 $l$ 个字符到第 $r$ 个字符的连续一段字符序列，其中下标从 $1$ 开始，满足 $1 \le l \le r \le |s|$。

现在，请你求出字符串 $s$ 的 所有子串 的 $\operatorname{Porder}$ 值之和。

Input

输入仅一行，包含一个字符串 $s$ $(1 \le |s| \le 10^5)$，保证字符串中仅包含小写字母。

Output

输出一行一个整数，表示 $s$ 的所有子串的 $\operatorname{Porder}$ 值之和。

Examples

Input 1

aa

Output 1

4

Input 2

abcdba

Output 2

9

Note

以样例 2 为例：

• $\operatorname{Porder}$ 值为 $2$ 的子串有：abcdba（共 $1$ 个）。
• $\operatorname{Porder}$ 值为 $1$ 的子串有：bcdb，以及所有长度为 $1$ 的子串（共 $7$ 个）。
• 其余子串的 $\operatorname{Porder}$ 值均为 $0$。

因此，所有子串的 $\operatorname{Porder}$ 值之和为 $1 \times 2 + 7 \times 1 + 0 = 9$。