No submission language available for this problem.

Description

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.

Samples

1
7 1
1

2
2 1
3 1

1
7 1
2

1
2 1

1
2 100000000000000000
10000000000000000

1
2 90000000000000000

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.