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^{5}$) — 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^{6}; 1 ≤ *a*_{*i*} ≤ 10^{17}$) — another prime divisor of number $*n*$ and its power in the canonical representation. The sum of all $*a*_{*i*}$ doesn't exceed $10^{17}$. Prime divisors in the input follow in the strictly increasing order.

The last line contains integer $*k*$ ($1 ≤ *k* ≤ 10^{18}$).

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.