E. On Iteration of One Well-Known Functiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputOf 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.InputThe 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).OutputIn 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.ExamplesInput17 11Output22 13 1Input17 12Output12 1Input12 10000000000000000010000000000000000Output12 90000000000000000NoteYou 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.
Input17 11
Output22 13 1
['math']