Migrated from Lutece 3069 爱情基金

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

罗先生在他的车上给罗女士承诺了 $80$ 万的爱情基金，但是爱情基金存在银行卡里面。罗女士不知道银行卡的密码，于是她找罗先生，罗先生给了她一封情书（情书以字符串 $S$ 来表示），然后问罗女士，这封情书一共有多少个本质不同的回文子串？

罗女士不仅生性果决隐忍坚毅，而且异常聪慧，很快就回答出来了。

可惜答案并不是银行卡的密码。

罗先生又问罗女士，这封情书一共有多少对非空回文子串，满足每对回文子串不相交？罗先生说，这道题的答案就是银行卡的密码。

罗女士非常想去美国，但是她没有钱买飞机票，只能动用爱情基金。于是罗女士找到了聪明的你，来算出银行卡的密码。

罗先生会把爱情基金存放在多张银行卡中，并且对于每一张银行卡会写一封对应的情书，所以你需要帮罗女士算出所有银行卡的密码。

Input

本题包含多组数据，每组数据为一行一个仅由小写英文字母构成的字符串 $S$，表示罗先生的情书。

Output

对于每组数据，输出一行一个整数，代表每封情书一共有多少对不相交的非空回文子串。

Samples

iloveu
aaaa

15
15

Constraints

$1\leq |S| \leq 100000$ $\sum |S| \leq 200000$

Note

2月14日，罗女士收到了罗先生的信物，她收到了美国嘉宾的邀请，太好了。

Resources

2023 UESTC ICPC Training for String