403863: GYM101343 E Abdalrahman Ali Bugs

E. Abdalrahman Ali Bugstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Abdalrahman Ali is one of the best ACMers in JUST, after the last contest he got a lot of simple bugs. So he decided to train him self to be more careful in writing solutions, he started to play simple games to make his mind more trained to write correct and perfect codes without bugs.

The first simple game he plays was as following; the game gives Abdalrahman a string S consisting of lowercase English letters. He has to find X such that it will result the minimal cost of the string.

He can find the cost of string S by applying this equation:

where f_i is the number of repetition of i^th letter and X is a positive number larger than 1.

Abdulrahman already found the solution, Can you find it now?

Input

The only line of input contains a string S of length between 1 and 10⁵ consisting of lowercase English letters.

Output

Print X the solution of the problem which will produce the minimal cost of string S. If there are multiple valid solutions, print the minimal one.

ExamplesInput

acm

Output

2

Input

aababaa

Output

5

Input

abcabcabc

Output

3