Consider the decimal representation of a natural number N.
Find the greatest common divisor (GCD) of all numbers that can be obtained by permuting the digits in the given number. Leading zeroes are allowed.

Input

Every line of input contains an integer, representing the original number N(0 < N < 10^250).

Output

For every test case, print the GCD of all numbers, which can be obtained from the given one by permuting the digits.

Score

Score is the length of your source.

Example

Input:
21
3
Output:
3
3