On Iteration of One Well-Known Function - Problem

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.

Examples

Input

1
7 1
1

Output

2
2 1
3 1

Input

1
7 1
2

Output

1
2 1

Input

1
2 100000000000000000
10000000000000000

Output

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.

3149: On Iteration of One Well-Known Function

Description

Source/Category