B. GCD of Substrings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Fedya was very happy to learn about the concept of GCD (Greatest Common Divisor) of numbers.

The greatest common divisor (GCD) of two natural numbers $$$m$$$ and $$$n$$$ is the largest of their common divisors. The concept of the greatest common divisor is naturally extended to sets of more than two natural numbers, as the greatest of the common divisors of all these numbers.

But what is the GCD of a single number? Let's assume that for natural numbers, it is the number itself. However, Fedya doesn't like such a boring generalization and he came up with his own concept - GSD.

Let's call the greatest substring divisor (GSD) of a number the greatest common divisor of all its non-empty substrings.

A substring is a continuous sequence of characters within a string. For example, for the number $$$171$$$, the substrings are: $$$1$$$, $$$17$$$, $$$171$$$, $$$7$$$, $$$71$$$, and $$$1$$$, while the numbers $$$11$$$ and $$$2$$$ are not its substrings.

Given a natural number $$$n$$$ $$$(1 \le n \le 10^{10^6})$$$, find its GSD.

Input

There is a single natural number $$$n$$$ $$$(1 \le n \le 10^{10^6})$$$. It is guaranteed that $$$n$$$ does not contain $$$0$$$.

Output

Output the GSD($$$n$$$).

Examples
Input
6
Output
6
Input
28
Output
2
Input
171
Output
1
Note

The condition presents all substrings of the number $$$171$$$ from the third example, their GCD is equal to $$$1$$$.