Migrated from Lutece 3072 Obsession

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

Enthrallo 是一位作曲家，同时也是一位强迫症患者。 他的曲子必须是由某个旋律反复拼接组成的。

准确地说，一首曲子如果用只含小写字母的字符串表示，那么这个字符串必须能够被划分成若干个（至少两个）完全相同的子串。比如 abab 能够被划分成两个 ab 子串，而 ababa 则多了一个丑陋的音符，它无法被划分成若干个完全相同的子串。

Enthrallo 现在创造了一首新曲子，但这首曲子十分长，你的任务就是帮助他计算这首曲子至少还要新加多少个音符才能符合他的期望。

Input

一行一个字符串 $S$，表示 Enthrallo 的新曲子。保证 $S$ 只包含小写英文字母。

Output

一行一个整数，表示 Enthrallo 至少还要新加多少个音符。

Samples

abab

0

ababa

1

Constraints

$1 \leq |S| \leq 10^7$

Resources

2023 UESTC ICPC Training for String