Periodic Strings

Interview

Time limit2sMemory limit512 MB

Summary

Given a string, find the smallest k such that cutting it into blocks of length k makes each block a one-step rotation of the previous block.

Level: Medium4 of 10
Topics: String, Brute force, Implementation, Math
Solved: No attempts yet

Problem

Define a $k$ -periodic string as follows.

A string $s$ is $k$ -periodic if its length $|s|$ is a multiple of $k$ and, when you cut $s$ into $|s|/k$ pieces of length $k$ , every piece except the first equals the previous piece with its last character moved to the front.

For example, abccabbcaabc is $3$ -periodic. It cuts into abc, cab, bca, abc, and every piece except the first is the previous piece rotated by one character (abc $\rightarrow$ cab, cab $\rightarrow$ bca, bca $\rightarrow$ abc).

Given a string $s$ , find the smallest $k$ for which $s$ is $k$ -periodic.

Input

The first line contains a string $s$ consisting only of lower-case letters ( $1 \leq |s| \leq 100$ ).

Output

Print, on a single line, the smallest $k$ for which the input string is $k$ -periodic.

Examples4

Example 1
Input
```
aaaaaaaa
```
Expected output
```
1
```
Example 2
Input
```
abbaabbaabba
```
Expected output
```
2
```
Example 3
Input
```
abcdef
```
Expected output
```
6
```
Example 4
Input
```
abccabbcaabc
```
Expected output
```
3
```