Натуральное число x называется точной степенью, если существуют такие натуральные числа a и b (b > 1), что x = a в степени b (a^b). Заметим, однако, что указанные числа a и b могут определяться неоднозначно.
Например, 16 = 2^4 = 4^2 ,
то есть для x = 16 существуют две такие пары (a, b).
Ваша задача состоит в том, чтобы найти все такие пары a,b что x = a^b.

Формат входного файла

Входной файл содержит целое число x (2 <= x <= 10^9)

Формат выходного файла

В первой строке выходного файла выведите число k искомых пар (a, b).
В каждой из последующих k строк выведите два числа:
ai и bi.

Примеры

power.in power.in
3 16

power.out power.out
0 2
2 4
4 2