#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return a > val ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
const int MAXN = 1000010;
int fl[MAXN];
int sp[MAXN];
void Sieve() {
  for (int i = 2; i < MAXN; i += 2) sp[i] = 2;
  for (int i = 3; i < MAXN; i += 2)
    if (!fl[i]) {
      sp[i] = i;
      for (int j = i; (long long)i * j < MAXN; j += 2)
        if (!fl[i * j]) {
          fl[i * j] = 1;
          sp[i * j] = i;
        }
    }
}
const int maxn = 1000010;
int n;
long long k;
vector<pair<long long, long long> > g[maxn];
long long ans[maxn];
void solve() {
  Sieve();
  cin >> n;
  for (int i = (0); i < (n); i++) {
    int p;
    long long a;
    cin >> p >> a;
    g[p].push_back(make_pair(0, a - 1));
  }
  cin >> k;
  for (int i = (maxn)-1; i >= (1); i--)
    if (int((g[i]).size())) {
      sort((g[i]).begin(), (g[i]).end());
      vector<pair<long long, long long> > tmp;
      for (int j = (0); j < (int((g[i]).size())); j++) {
        if (int((tmp).size()) && tmp.back().second + 1 >= g[i][j].first) {
          tmp.back().second += g[i][j].second - g[i][j].first + 1;
        } else {
          tmp.push_back(g[i][j]);
        }
      }
      g[i].clear();
      for (int j = (0); j < (int((tmp).size())); j++) {
        if (tmp[j].first >= k) {
          ans[i] += tmp[j].second - tmp[j].first + 1;
        } else if (tmp[j].second >= k) {
          ans[i] += tmp[j].second - k + 1;
          g[i].push_back(make_pair(tmp[j].first, k - 1));
        } else {
          g[i].push_back(tmp[j]);
        }
      }
      for (int j = (0); j < (int((g[i]).size())); j++) {
        int t = i - 1;
        while (t > 1) {
          int l = sp[t];
          g[l].push_back(make_pair(g[i][j].first + 1, g[i][j].second + 1));
          t /= l;
        }
      }
    }
  vector<pair<int, long long> > vans;
  for (int i = (0); i < (maxn); i++)
    if (ans[i]) {
      vans.push_back(make_pair(i, ans[i]));
    }
  cout << int((vans).size()) << "\n";
  for (int i = (0); i < (int((vans).size())); i++) {
    cout << vans[i].first << " " << vans[i].second << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 ≤ 105) — 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 pi, ai (2 ≤ pi ≤ 106; 1 ≤ ai ≤ 1017) — another prime divisor of number n and its power in the canonical representation. The sum of all ai doesn't exceed 1017. Prime divisors in the input follow in the strictly increasing order.

The last line contains integer k (1 ≤ k ≤ 1018).

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 qi, bi (bi ≥ 1) — another prime divisor and its power in the canonical representaion of the result. Numbers qi 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return a > val ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
const int MAXN = 1000010;
int fl[MAXN];
int sp[MAXN];
void Sieve() {
  for (int i = 2; i < MAXN; i += 2) sp[i] = 2;
  for (int i = 3; i < MAXN; i += 2)
    if (!fl[i]) {
      sp[i] = i;
      for (int j = i; (long long)i * j < MAXN; j += 2)
        if (!fl[i * j]) {
          fl[i * j] = 1;
          sp[i * j] = i;
        }
    }
}
const int maxn = 1000010;
int n;
long long k;
vector<pair<long long, long long> > g[maxn];
long long ans[maxn];
void solve() {
  Sieve();
  cin >> n;
  for (int i = (0); i < (n); i++) {
    int p;
    long long a;
    cin >> p >> a;
    g[p].push_back(make_pair(0, a - 1));
  }
  cin >> k;
  for (int i = (maxn)-1; i >= (1); i--)
    if (int((g[i]).size())) {
      sort((g[i]).begin(), (g[i]).end());
      vector<pair<long long, long long> > tmp;
      for (int j = (0); j < (int((g[i]).size())); j++) {
        if (int((tmp).size()) && tmp.back().second + 1 >= g[i][j].first) {
          tmp.back().second += g[i][j].second - g[i][j].first + 1;
        } else {
          tmp.push_back(g[i][j]);
        }
      }
      g[i].clear();
      for (int j = (0); j < (int((tmp).size())); j++) {
        if (tmp[j].first >= k) {
          ans[i] += tmp[j].second - tmp[j].first + 1;
        } else if (tmp[j].second >= k) {
          ans[i] += tmp[j].second - k + 1;
          g[i].push_back(make_pair(tmp[j].first, k - 1));
        } else {
          g[i].push_back(tmp[j]);
        }
      }
      for (int j = (0); j < (int((g[i]).size())); j++) {
        int t = i - 1;
        while (t > 1) {
          int l = sp[t];
          g[l].push_back(make_pair(g[i][j].first + 1, g[i][j].second + 1));
          t /= l;
        }
      }
    }
  vector<pair<int, long long> > vans;
  for (int i = (0); i < (maxn); i++)
    if (ans[i]) {
      vans.push_back(make_pair(i, ans[i]));
    }
  cout << int((vans).size()) << "\n";
  for (int i = (0); i < (int((vans).size())); i++) {
    cout << vans[i].first << " " << vans[i].second << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

```