题目描述

一个长度为 $n$ 的字符串 $s$ 被叫做 $k$ 阶级回文串，当且仅当它本身是一个回文串，而且它长度为 $⌊\frac{n}{2}⌋$ 的前缀和后缀都是 $k−1$ 阶级回文串。任何一个字符串（包括空字符串）都至少是 $0$ 阶级字符串。举例来说，$abaaba$ 是 $3$ 阶级字符串。

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

输入格式

一个长度不超过 $5\times 10^6$ 的非空字符串。

输出格式

一个整数表示答案。

a2A

1

abacaba

6