A9461. 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.

The first line contains integer $m$ ( $1<=m<=10^{5}$ ) — 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}<=10^{6}; 1<=a_{i}<=10^{17}$ ) — another prime divisor of number $n$ and its power in the canonical representation. The sum of all $a_{i}$ doesn't exceed $10^{17}$ . Prime divisors in the input follow in the strictly increasing order.

The last line contains integer $k$ ( $1<=k<=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.

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.