#include <bits/stdc++.h>
using namespace std;
template <class T>
using rque = priority_queue<T, vector<T>, greater<T>>;
const long long mod = (int)1e9 + 7;
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmax(T &a, const T &b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  if (b == 0) return a;
  long long c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}
long long extGCD(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extGCD(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
struct UnionFind {
  vector<long long> data;
  int num;
  UnionFind(int sz) {
    data.assign(sz, -1);
    num = sz;
  }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return (false);
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    num--;
    return (true);
  }
  int find(int k) {
    if (data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
  long long size(int k) { return (-data[find(k)]); }
};
long long M = 1000000007;
template <int mod>
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  ModInt &operator+=(const ModInt &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }
  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }
  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
  static int get_mod() { return mod; }
};
using mint = ModInt<mod>;
mint mpow(long long x, long long n) {
  mint ans = 1;
  while (n != 0) {
    if (n & 1) ans *= x;
    x = x * x % mod;
    n = n >> 1;
  }
  return ans;
}
long long mpow2(long long x, long long n, long long mod) {
  long long ans = 1;
  while (n != 0) {
    if (n & 1) ans = ans * x % mod;
    x = x * x % mod;
    n = n >> 1;
  }
  return ans;
}
vector<mint> fac;
vector<mint> ifac;
void setcomb(int sz = 2000010) {
  fac.assign(sz + 1, 0);
  ifac.assign(sz + 1, 0);
  fac[0] = 1;
  for (long long i = 0; i < sz; i++) {
    fac[i + 1] = fac[i] * (i + 1);
  }
  ifac[sz] = fac[sz].inverse();
  for (long long i = sz; i > 0; i--) {
    ifac[i - 1] = ifac[i] * i;
  }
}
mint comb(long long a, long long b) {
  if (fac.size() == 0) setcomb();
  if (a == 0 && b == 0) return 1;
  if (a < b || a < 0) return 0;
  return ifac[a - b] * ifac[b] * fac[a];
}
mint perm(long long a, long long b) {
  if (fac.size() == 0) setcomb();
  if (a == 0 && b == 0) return 1;
  if (a < b || a < 0) return 0;
  return fac[a] * ifac[a - b];
}
long long modinv(long long a) {
  long long b = M, u = 1, v = 0;
  while (b) {
    long long t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= M;
  if (u < 0) u += M;
  return u;
}
long long modinv2(long long a, long long mod) {
  long long b = mod, u = 1, v = 0;
  while (b) {
    long long t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= mod;
  if (u < 0) u += mod;
  return u;
}
int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n = 1000000;
  bool isp[n + 10];
  for (long long i = 0; i < (n + 10); i++) isp[i] = 1;
  vector<int> prime;
  isp[0] = 0, isp[1] = 0;
  for (long long i = 2; i < (n + 1); i++) {
    if (isp[i]) {
      for (long long j = i * 2; j <= n; j += i) isp[j] = 0;
      prime.push_back(i);
    }
  }
  map<long long, long long> mp;
  for (long long i = 0; i < (prime.size()); i++) mp[prime[i]] = i;
  vector<pair<long long, long long>> li[prime.size()];
  for (long long i = 0; i < (prime.size()); i++) {
    int cp = prime[i] - 1;
    for (long long j = 0; prime[j] * prime[j] <= cp; j++) {
      if (cp % prime[j] == 0) {
        long long cnt = 0;
        while (cp % prime[j] == 0) {
          cp /= prime[j];
          cnt++;
        }
        li[i].push_back({mp[prime[j]], cnt});
      }
    }
    if (cp > 1) li[i].push_back({mp[cp], 1});
  }
  long long np = prime.size();
  long long m;
  cin >> m;
  long long p, a;
  vector<pair<long long, long long>> v[np];
  for (long long i = 0; i < (m); i++) cin >> p >> a, v[mp[p]].push_back({0, a});
  long long k;
  cin >> k;
  long long ans[np];
  for (long long i = (long long)np - 1; i >= 0; i--) {
    sort(v[i].begin(), v[i].end());
    long long now = 0, stock = 0;
    for (long long j = 0; j < v[i].size();) {
      long long memo = v[i][j].first;
      if (memo - now > stock) {
        if (stock > 0) {
          for (auto &e : li[i])
            v[e.first].push_back({now + 1, stock * e.second});
        }
        now = memo;
        stock = 0;
      }
      for (; j < v[i].size(); j++) {
        if (v[i][j].first != memo) break;
        stock += v[i][j].second;
      }
    }
    if (min(stock, k - now) > 0) {
      for (auto &e : li[i])
        v[e.first].push_back({now + 1, min(stock, k - now) * e.second});
    }
    ans[i] = max(0ll, stock - (k - now));
  }
  vector<pair<long long, long long>> out;
  for (long long i = 0; i < (np); i++)
    if (ans[i] > 0) out.push_back({prime[i], ans[i]});
  cout << out.size() << endl;
  for (long long i = 0; i < (out.size()); i++)
    cout << out[i].first << " " << out[i].second << endl;
}

### Prompt

In cpp, your task is to solve the following 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 ≤ 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;
template <class T>
using rque = priority_queue<T, vector<T>, greater<T>>;
const long long mod = (int)1e9 + 7;
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmax(T &a, const T &b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  if (b == 0) return a;
  long long c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}
long long extGCD(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extGCD(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
struct UnionFind {
  vector<long long> data;
  int num;
  UnionFind(int sz) {
    data.assign(sz, -1);
    num = sz;
  }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return (false);
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    num--;
    return (true);
  }
  int find(int k) {
    if (data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
  long long size(int k) { return (-data[find(k)]); }
};
long long M = 1000000007;
template <int mod>
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  ModInt &operator+=(const ModInt &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }
  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }
  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
  static int get_mod() { return mod; }
};
using mint = ModInt<mod>;
mint mpow(long long x, long long n) {
  mint ans = 1;
  while (n != 0) {
    if (n & 1) ans *= x;
    x = x * x % mod;
    n = n >> 1;
  }
  return ans;
}
long long mpow2(long long x, long long n, long long mod) {
  long long ans = 1;
  while (n != 0) {
    if (n & 1) ans = ans * x % mod;
    x = x * x % mod;
    n = n >> 1;
  }
  return ans;
}
vector<mint> fac;
vector<mint> ifac;
void setcomb(int sz = 2000010) {
  fac.assign(sz + 1, 0);
  ifac.assign(sz + 1, 0);
  fac[0] = 1;
  for (long long i = 0; i < sz; i++) {
    fac[i + 1] = fac[i] * (i + 1);
  }
  ifac[sz] = fac[sz].inverse();
  for (long long i = sz; i > 0; i--) {
    ifac[i - 1] = ifac[i] * i;
  }
}
mint comb(long long a, long long b) {
  if (fac.size() == 0) setcomb();
  if (a == 0 && b == 0) return 1;
  if (a < b || a < 0) return 0;
  return ifac[a - b] * ifac[b] * fac[a];
}
mint perm(long long a, long long b) {
  if (fac.size() == 0) setcomb();
  if (a == 0 && b == 0) return 1;
  if (a < b || a < 0) return 0;
  return fac[a] * ifac[a - b];
}
long long modinv(long long a) {
  long long b = M, u = 1, v = 0;
  while (b) {
    long long t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= M;
  if (u < 0) u += M;
  return u;
}
long long modinv2(long long a, long long mod) {
  long long b = mod, u = 1, v = 0;
  while (b) {
    long long t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= mod;
  if (u < 0) u += mod;
  return u;
}
int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n = 1000000;
  bool isp[n + 10];
  for (long long i = 0; i < (n + 10); i++) isp[i] = 1;
  vector<int> prime;
  isp[0] = 0, isp[1] = 0;
  for (long long i = 2; i < (n + 1); i++) {
    if (isp[i]) {
      for (long long j = i * 2; j <= n; j += i) isp[j] = 0;
      prime.push_back(i);
    }
  }
  map<long long, long long> mp;
  for (long long i = 0; i < (prime.size()); i++) mp[prime[i]] = i;
  vector<pair<long long, long long>> li[prime.size()];
  for (long long i = 0; i < (prime.size()); i++) {
    int cp = prime[i] - 1;
    for (long long j = 0; prime[j] * prime[j] <= cp; j++) {
      if (cp % prime[j] == 0) {
        long long cnt = 0;
        while (cp % prime[j] == 0) {
          cp /= prime[j];
          cnt++;
        }
        li[i].push_back({mp[prime[j]], cnt});
      }
    }
    if (cp > 1) li[i].push_back({mp[cp], 1});
  }
  long long np = prime.size();
  long long m;
  cin >> m;
  long long p, a;
  vector<pair<long long, long long>> v[np];
  for (long long i = 0; i < (m); i++) cin >> p >> a, v[mp[p]].push_back({0, a});
  long long k;
  cin >> k;
  long long ans[np];
  for (long long i = (long long)np - 1; i >= 0; i--) {
    sort(v[i].begin(), v[i].end());
    long long now = 0, stock = 0;
    for (long long j = 0; j < v[i].size();) {
      long long memo = v[i][j].first;
      if (memo - now > stock) {
        if (stock > 0) {
          for (auto &e : li[i])
            v[e.first].push_back({now + 1, stock * e.second});
        }
        now = memo;
        stock = 0;
      }
      for (; j < v[i].size(); j++) {
        if (v[i][j].first != memo) break;
        stock += v[i][j].second;
      }
    }
    if (min(stock, k - now) > 0) {
      for (auto &e : li[i])
        v[e.first].push_back({now + 1, min(stock, k - now) * e.second});
    }
    ans[i] = max(0ll, stock - (k - now));
  }
  vector<pair<long long, long long>> out;
  for (long long i = 0; i < (np); i++)
    if (ans[i] > 0) out.push_back({prime[i], ans[i]});
  cout << out.size() << endl;
  for (long long i = 0; i < (out.size()); i++)
    cout << out[i].first << " " << out[i].second << endl;
}

```