CF396E.On Iteration of One Well-Known Function

Of course, many of you can calculate φ(n) — the number of positive integers that are less than or equal to n, that are coprime with n. But what if we need to calculate φ(φ(...φ(n))), where function φ is taken k times and n is given in the canonical decomposition into prime factors?

You are given n and k, calculate the value of φ(φ(...φ(n))). Print the result in the canonical decomposition into prime factors.

当然，你们中的许多人可以计算欧拉函数 φ(n) —— 即不超过 n 且与 n 互素的正整数的个数。但如果需要计算 φ(φ(...φ(n)))（其中欧拉函数 φ 共嵌套应用 k 次），且 n 以素因数标准分解形式给出，又该如何处理呢？

给定 n 和 k，请计算 φ(φ(...φ(n))) 的值，并将结果以素因数标准分解形式输出。

The first line contains integer m (1 ≤ m ≤ 105) — the number of distinct prime divisors in the canonical representaion of n.

Each of the next m lines contains a pair of space-separated integers p__i, a__i (2 ≤ p__i ≤ 106; 1 ≤ a__i ≤ 1017) — another prime divisor of number n and its power in the canonical representation. The sum of all a__i doesn't exceed 1017. Prime divisors in the input follow in the strictly increasing order.

The last line contains integer k (1 ≤ k ≤ 1018).

第一行包含一个整数 $m$（$1 \leq m \leq 10^5$）——即 $n$ 的标准分解式中不同质因数的个数。

接下来的 $m$ 行，每行包含一对以空格分隔的整数 $p_i,\,a_i$（$2 \leq p_i \leq 10^6$；$1 \leq a_i \leq 10^{17}$）——表示 $n$ 的另一个质因数及其在标准分解式中的幂次。所有 $a_i$ 的总和不超过 $10^{17}$。输入中给出的质因数严格按递增顺序排列。

最后一行包含一个整数 $k$（$1 \leq k \leq 10^{18}$）。

In the first line, print integer w — the number of distinct prime divisors of number φ(φ(...φ(n))), where function φ is taken k times.

Each of the next w lines must contain two space-separated integers q__i, b__i (b__i ≥ 1) — another prime divisor and its power in the canonical representaion of the result. Numbers q__i must go in the strictly increasing order.

第一行输出整数 $w$ —— 数 $φ(φ(...φ(n)))$ 的不同质因数的个数，其中函数 $φ$ 共应用 $k$ 次。

接下来的 $w$ 行中，每行需输出两个用空格分隔的整数 $q_i$、$b_i$（其中 $b_i \geq 1$）—— 分别表示结果在标准质因数分解形式中的另一个质因数及其对应的幂次。数字 $q_i$ 必须严格递增排列。

You can read about canonical representation of a positive integer here: http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic.

You can read about function φ(n) here: http://en.wikipedia.org/wiki/Euler's_totient_function.

你可以在以下链接阅读正整数的标准分解形式（即算术基本定理）：http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic。

你可以在以下链接阅读欧拉函数 φ(n) 的相关内容：http://en.wikipedia.org/wiki/Euler's_totient_function。