No tag edit access

The problem statement has recently been changed. View the changes.

×
E. On Iteration of One Well-Known Function

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard 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.

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.

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/12/2021 04:42:49 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|