В последнее время Уджан стал весьма ленивым, но наконец-то решил привести свой двор в порядок. Сначала он решил покрасить тропинку от своего дома до ворот.
Тропинка состоит из \(n\) последовательных плиток, пронумерованных от \(1\) до \(n\). Уджан покрасит каждую из плиток в некоторый цвет. Он считает, что тропинка эстетична, если каждые две различные плитки с номерами \(i\) и \(j\) такими, что \(|j - i|\) является делителем числа \(n\) строго большим \(1\), покрашены в одинаковые цвета. Формально, любые две плитки с номерами \(i\) и \(j\) должны быть покрашены в одинаковый цвет, если \(|i-j| > 1\) и \(n \bmod |i-j| = 0\) (где \(x \bmod y\) — это остаток при делении \(x\) на \(y\)).
Уджан хочет украсить своё место. В какое наибольшее количество цветов Уджан может покрасить тропинку таким образом, чтобы она была эстетичной?
Выходные данные
Выведите одно число — максимальное возможное количество цветов, в которое можно покрасить тропинку.
Примечание
В первом примере тропинку можно покрасить в максимум два цвета. Плитки \(1\) и \(3\) должны иметь одинаковый цвет, так как \(4 \bmod |3-1| = 0\). Плитки \(2\) и \(4\) тоже должны иметь одинаковый цвет, так как \(4 \bmod |4-2| = 0\).
Во втором примере могут быть использованы все пять цветов.
Примеры покрасок для первого и второго теста.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
|
2
|
|
2
|
5
|
5
|