我们定义一种作用于字符串的操作，称为“折叠”。折叠由若干次（可能为零次）折叠动作组成。每次折叠发生在两个相邻字符之间，将字符串的后半部分（距离字符串开头较远的部分）翻转并放置在前半部分（距离字符串开头较近的部分）之上，使其与折叠位置对齐。通过这种操作，字符串被转换为一个层数比折叠次数多一层的结构。

折叠后，字符串可以看作是若干堆字符。如果同一堆中的所有字符都相同，我们称该折叠是“有效的”。

折叠的“对应集合”是指折叠位置在原字符串中紧邻的前一个字符的位置集合。例如，在第 2 个字符和第 3 个字符之间进行一次折叠，其对应集合为 $\{2\}$；零次折叠的对应集合为空集。仅当两个折叠的对应集合相同时，才认为这两个折叠是相同的。

如果存在整数 $a$ 和 $b$ ($0 \le b < a$)，使得对于字符串长度 $n$，满足 $x \in S \iff 1 \le x < n, x \equiv b \pmod a$，则称集合 $S$ 是“等差的”。例如，当 $n=10$ 时，集合 $\emptyset, \{2\}, \{1, 9\}, \{2, 4, 6, 8\}$ 是等差的，而 $\{1, 2, 4\}, \{1, 5\}, \{7, 8, 9\}$ 则不是。

如果一个折叠既是有效的，其对应集合又是等差的，则称该折叠是“极好的”。请参阅下一页的图片以获得更直观的理解。

给定一个字符串，计算该字符串中极好折叠的数量。

输入格式

仅一行，包含一个长度为 $n$ ($1 \le n \le 10^6$) 的字符串，由拉丁字母、数字、下划线或连字符组成。

输出格式

输出一个整数，即给定字符串中极好折叠的数量。

样例

样例输入 1

aaaaa

样例输出 1

9

样例输入 2

V-oo-V

样例输出 2

2

样例输入 3

gritukan

样例输出 3

1

样例输入 4

Lhic

样例输出 4

1

样例输入 5

000000000000000000000000

样例输出 5

6

样例输入 6

SpyCheessee

样例输出 6

3

样例输入 7

Aa

样例输出 7

1

样例输入 8

228322

样例输出 8

4

样例输入 9

______________________________________

样例输出 9

380

说明

在第一个样例中，极好折叠的对应集合为：$\emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{1, 3\}, \{1, 4\}, \{2, 4\}, \{1, 2, 3, 4\}$。

这是字符串 "aabccbaa" 的一个极好折叠。对应集合为 $\{1, 4, 7\}$。

这是字符串 "abc" 的一个极好折叠。对应集合为 $\emptyset$。

这不是一个有效的折叠，但它是一个折叠，且具有等差的对应集合。对应集合为 $\{2, 6, 10\}$。

这不是一个折叠，因为上半部分与下半部分运行方向相同。

这不是一个折叠，因为上半部分要么运行方向相同（如果我们认为它向右运行），要么未对齐（如果我们认为它向左运行）。

这是一个有效的折叠，但其对应集合不是等差的。对应集合为 $\{4, 6\}$。