CodeForces 396E On Iteration o_牛客题霸

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 ≤ 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 pi, ai (2 ≤ pi ≤ 106; 1 ≤ ai ≤ 1017) — another prime divisor of number n and its power in the canonical representation. The sum of all ai doesn't exceed 1017. Prime divisors in the input follow in the strictly increasing order.The last line contains integer k (1 ≤ k ≤ 1018).

输出描述:

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 qi, bi(bi ≥ 1) — another prime divisor and its power in the canonical representaion of the result. Numbers qi must go in the strictly increasing order.

示例1

输入

1<br />7 1<br />1<br />1<br />7 1<br />2<br />1<br />2 100000000000000000<br />10000000000000000<br />

输出

2<br />2 1<br />3 1<br />1<br />2 1<br />1<br />2 90000000000000000<br />

备注:

You can read about canonical representation of a positive integer here: http:en.wikipedia.orgwikiFundamental_theorem_of_arithmetic.You can read about function φ(n) here: http:en.wikipedia.orgwikiEuler's_totient_function.