Distinct Repeating Strings

Given a text t, you are asked to find out the number of unique non-empty repeating strings present in t. Repeating strings can be formed by concatenating the same string s to itself β†’ s + s.

Input

The first line of the input contains the text t (1 ≀ |t| ≀ 1000).

Output

The program should print the number of repeating strings present in t.

Examples

Input
Output
yeeey
1
abcabcabc
3

Explanation

  1. yeeey β†’ ee
  1. abcabcabc β†’ abcabc, bcabca, cabcab
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in