Задача Точная степень

Описание

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

Например, 16 = 2 ⁴ = 4 ² , то есть для x = 16 существуют две такие пары (a, b).

Ваша задача состоит в том, чтобы найти все такие пары (a _i , b _i ), что x = a _i ^{b _i}

Формат входных данных

Входной файл содержит целое число x (2 ≤ x ≤ 10 ⁹ ).

Формат выходных данных

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