Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8821

Jo'natishlar soni: 714441

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1174


So'ngi izohlar

731. Power Strings
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

Given two strings a and b we define a*b to be their concatenation.

   For example, if a = "abc" and b = "def" then a*b = "abcdef".

   If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way:

a0 = “” (empty line)

an+1 = a * an

   For a given string s print the largest n such that s = an for some string a.

Input

Input contain a line representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 105 characters.

Output

   For input string s print in first line the largest n such that s = an for some string a.

Samples

Input

Output

1

abcd

1

2

aaaa

4

3

ababab

3

 

Tayyorladi: Azat Yusupov
Text from: e-olimp.com
Mening urinishlarim(0) Muhokama (0) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(30) Barcha urinishlar(92)