该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一个长度为 $n$ 的字符串 $s$ 被叫做 $k$ 阶级回文串，当且仅当它本身是一个回文串，而且它长度为 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 的前缀和后缀都是 $k-1$ 阶级回文串。任何一个字符串（包括空字符串）都至少是 $0$ 阶级字符串。

举例来说，abaaba 是 $3$ 阶级字符串。

现在给定一个字符串，请求出其所有前缀的的阶级之和。

输入格式

一行，一个非空的字符串。

输出格式

一个整数，表示该字符串的回文度数。

【样例 1 输入】

a2A

【样例 1 输出】

1

【样例 2 输入】

abacaba

【样例 2 输出】

6

【数据范围】

数据范围与提示

对于 $40\%$ 的数据，$n\le 300$；

对于 $70\%$ 的数据，$n\le 10^3$；

对于 $100\%$ 的数据，$n\le 10^5$，字符全是小写字母。