PIPI研究了多年字符串后发现回文串是字符串中最优雅的一种存在了。所以PIPI发明了一种指标叫优雅度的指标来衡量一个字符串的优雅程度。优雅度定义如下：
1.空串和非回文串的优雅度为0。
2.一个长度为len的回文串的优雅度为，其长度为len/2(向下取整)的前缀和后缀的优雅度+1.
例如串"baabbaab"的优雅度为2，“babbab”的优雅度为3.
现在PIPI有一个长度为n的字符串，请你求出这个字符串的每一个前缀的优雅度的总和。

第一行为一个整数n，表示串长。（n<=1e6）
第二行给出一个字符串，仅包含大写、小写字母以及数字。

输出一个数字，表示答案。