Многие из вас, конечно, умеют считать φ(n) — количество целых положительных чисел, меньших либо равных n, которые взаимно просты с n. А что, если нужно посчитать φ(φ(...φ(n))), где функция φ берется k раз, а n задано в каноническом разложении на простые множители?
Посчитайте значение функции φ(φ(...φ(n))) для заданных n и k. Результат требуется вывести в каноническом разложении на простые множители.
Выходные данные
В первой строке выведите целое число w — количество различных простых делителей числа φ(φ(...φ(n))), где функция φ берется k раз.
В следующих w строках через пробел выведите пары целых чисел qi, bi (bi ≥ 1) — очередной простой делитель результата и степень, в которой он входит в результат. Числа qi должны идти в строго возрастающем порядке.
Примечание
О каноническом разложении числа на простые множители можно прочитать здесь: http://ru.wikipedia.org/wiki/Основная_теорема_арифметики.
О функции φ(n) можно прочитать здесь: http://ru.wikipedia.org/wiki/Функция_Эйлера.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
7 1
1
|
2
2 1
3 1
|
|
2
|
1
7 1
2
|
1
2 1
|
|
3
|
1
2 100000000000000000
10000000000000000
|
1
2 90000000000000000
|