E. Об итерации одной известной функции
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Многие из вас, конечно, умеют считать φ(n) — количество целых положительных чисел, меньших либо равных n, которые взаимно просты с n. А что, если нужно посчитать φ(φ(...φ(n))), где функция φ берется k раз, а n задано в каноническом разложении на простые множители?

Посчитайте значение функции φ(φ(...φ(n))) для заданных n и k. Результат требуется вывести в каноническом разложении на простые множители.

Входные данные

В первой строке задается целое число m (1 ≤ m ≤ 105) — количество различных простых делителей, участвующих в разложении числа n.

В каждой из следующих m строк записана пара целых чисел pi, ai (2 ≤ pi ≤ 106; 1 ≤ ai ≤ 1017), разделенные пробелом, — очередной простой делитель числа n и степень, в которой он в него входит. Сумма всех ai не превосходит 1017. Простые делители во входных данных идут в строго возрастающем порядке.

В последней строке задано целое число k (1 ≤ k ≤ 1018).

Выходные данные

В первой строке выведите целое число w — количество различных простых делителей числа φ(φ(...φ(n))), где функция φ берется k раз.

В следующих w строках через пробел выведите пары целых чисел qi, bi (bi ≥ 1) — очередной простой делитель результата и степень, в которой он входит в результат. Числа qi должны идти в строго возрастающем порядке.

Примеры
Входные данные
1
7 1
1
Выходные данные
2
2 1
3 1
Входные данные
1
7 1
2
Выходные данные
1
2 1
Входные данные
1
2 100000000000000000
10000000000000000
Выходные данные
1
2 90000000000000000
Примечание

О каноническом разложении числа на простые множители можно прочитать здесь: http://ru.wikipedia.org/wiki/Основная_теорема_арифметики.

О функции φ(n) можно прочитать здесь: http://ru.wikipedia.org/wiki/Функция_Эйлера.