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
Sign in to continue