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.

Input

The first line contains integer m (1 ≤ m ≤ 10⁵) — 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⁶; 1 ≤ a_i ≤ 10¹⁷) — another prime divisor of number n and its power in the canonical representation. The sum of all a_i doesn't exceed 10¹⁷. Prime divisors in the input follow in the strictly increasing order.

The last line contains integer k (1 ≤ k ≤ 10¹⁸).

Output

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.

Note

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.

On Iteration of One Well-Known Function

Examples