Число x є повним квадратом, якщо для деякого цілого b, x = b2. Аналогічно x є точним кубом, якщо для деякого цілого b, x = b3. Надалі будемо стверджувати, що x є точним p-им степенем, якщо існує таке ціле b, що x = bp. За заданим цілим x необхідно знайти найбільше p, для якого x є точним p-им степенем.

Вхідні дані

На вході одне число - 32-бітове ціле знакове x, |x| > 1.

Вихідні дані

Вивести найбільше p, для якого x є точним p-им степенем.