В последнее время Уджан стал весьма ленивым, но наконец-то решил привести свой двор в порядок. Сначала он решил покрасить тропинку от своего дома до ворот.

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

Уджан хочет украсить своё место. В какое наибольшее количество цветов Уджан может покрасить тропинку таким образом, чтобы она была эстетичной?