description: Mocha wants to be an astrologer. There are n stars which can be seen in Zhijiang, and the brightness of the i-th star is a_i. 
  
  Mocha considers that these n stars form a constellation, and she uses (a_1,a_2,…,a_n) to show its state. A state is called mathematical if all of the following three conditions are satisfied:
  
    * For all i (1≤ i≤ n), a_i is an integer in the range [l_i, r_i].
    * ∑  _{i=1} ^ n a_i ≤ m.
    * \gcd(a_1,a_2,…,a_n)=1.
  
  
  
  Here, \gcd(a_1,a_2,…,a_n) denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers a_1,a_2,…,a_n.
  
  Mocha is wondering how many different mathematical states of this constellation exist. Because the answer may be large, you must find it modulo 998 244 353.
  
  Two states (a_1,a_2,…,a_n) and (b_1,b_2,…,b_n) are considered different if there exists i (1≤ i≤ n) such that a_i ≠ b_i.
  
  Input
  
  The first line contains two integers n and m (2 ≤ n ≤ 50, 1 ≤ m ≤ 10^5) — the number of stars and the upper bound of the sum of the brightness of stars.
  
  Each of the next n lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ m) — the range of the brightness of the i-th star.
  
  Output
  
  Print a single integer — the number of different mathematical states of this constellation, modulo 998 244 353.
  
  Examples
  
  Input
  
  
  2 4
  1 3
  1 2
  
  
  Output
  
  
  4
  
  Input
  
  
  5 10
  1 10
  1 10
  1 10
  1 10
  1 10
  
  
  Output
  
  
  251
  
  Input
  
  
  5 100
  1 94
  1 96
  1 91
  4 96
  6 97
  
  
  Output
  
  
  47464146
  
  Note
  
  In the first example, there are 4 different mathematical states of this constellation:
  
    * a_1=1, a_2=1.
    * a_1=1, a_2=2.
    * a_1=2, a_2=1.
    * a_1=3, a_2=1.
solution: #include <bits/stdc++.h>
  using namespace std;
  template <long long mod>
  struct modular {
    long long value;
    modular(long long x = 0) {
      value = x % mod;
      if (value < 0) value += mod;
    }
    modular& operator+=(const modular& other) {
      if ((value += other.value) >= mod) value -= mod;
      return *this;
    }
    modular& operator-=(const modular& other) {
      if ((value -= other.value) < 0) value += mod;
      return *this;
    }
    modular& operator*=(const modular& other) {
      value = value * other.value % mod;
      return *this;
    }
    modular& operator/=(const modular& other) {
      long long a = 0, b = 1, c = other.value, m = mod;
      while (c != 0) {
        long long t = m / c;
        m -= t * c;
        swap(c, m);
        a -= t * b;
        swap(a, b);
      }
      a %= mod;
      if (a < 0) a += mod;
      value = value * a % mod;
      return *this;
    }
    modular operator+(const modular& rhs) const { return modular(*this) += rhs; }
    modular operator-(const modular& rhs) const { return modular(*this) -= rhs; }
    modular operator*(const modular& rhs) const { return modular(*this) *= rhs; }
    modular operator/(const modular& rhs) const { return modular(*this) /= rhs; }
    modular& operator++() { return *this += 1; }
    modular& operator--() { return *this -= 1; }
    modular operator++(int) {
      modular res(*this);
      *this += 1;
      return res;
    }
    modular operator--(int) {
      modular res(*this);
      *this -= 1;
      return res;
    }
    modular operator-() const { return modular(-value); }
    bool operator==(const modular& rhs) const { return value == rhs.value; }
    bool operator!=(const modular& rhs) const { return value != rhs.value; }
    bool operator<(const modular& rhs) const { return value < rhs.value; }
  };
  template <long long mod>
  string to_string(const modular<mod>& x) {
    return to_string(x.value);
  }
  template <long long mod>
  ostream& operator<<(ostream& stream, const modular<mod>& x) {
    return stream << x.value;
  }
  template <long long mod>
  istream& operator>>(istream& stream, modular<mod>& x) {
    stream >> x.value;
    x.value %= mod;
    if (x.value < 0) x.value += mod;
    return stream;
  }
  constexpr long long mod = 998244353LL;
  using mint = modular<mod>;
  mint power(mint a, long long n) {
    mint res = 1;
    while (n > 0) {
      if (n & 1) {
        res *= a;
      }
      a *= a;
      n >>= 1;
    }
    return res;
  }
  vector<mint> fact(1, 1);
  vector<mint> finv(1, 1);
  mint C(int n, int k) {
    if (n < k || k < 0) {
      return mint(0);
    }
    while ((int)fact.size() < n + 1) {
      fact.emplace_back(fact.back() * (int)fact.size());
      finv.emplace_back(mint(1) / fact.back());
    }
    return fact[n] * finv[k] * finv[n - k];
  }
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    const int MAX = 100001;
    vector<int> primes;
    vector<int> spf(MAX);
    vector<bool> is_prime(MAX, true);
    is_prime[0] = is_prime[1] = false;
    spf[0] = spf[1] = 1;
    for (int i = 2; i < MAX; i++) {
      if (!is_prime[i]) {
        continue;
      }
      primes.emplace_back(i);
      spf[i] = i;
      if (1LL * i * i >= MAX) {
        continue;
      }
      for (int j = i * i; j < MAX; j += i) {
        if (is_prime[j]) {
          is_prime[j] = false;
          spf[j] = i;
        }
      }
    }
    int n, m;
    cin >> n >> m;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
      cin >> l[i] >> r[i];
    }
    vector<mint> a(m + 1);
    vector<vector<mint>> dp(m + 1);
    for (int i = 1; i <= m; i++) {
      dp[i] = vector<mint>(m / i + 1);
      dp[i][0] = 1;
    }
    for (int k = 0; k < n; k++) {
      for (int i = 1; i <= m; i++) {
        int x = (l[k] + i - 1) / i;
        int y = r[k] / i;
        vector<mint> new_dp(m / i + 1);
        for (int j = 0; j <= m / i; j++) {
          if (j != 0) {
            new_dp[j] = new_dp[j - 1];
          }
          if (j >= x) {
            new_dp[j] += dp[i][j - x];
          }
          if (j >= y + 1) {
            new_dp[j] -= dp[i][j - y - 1];
          }
        }
        swap(dp[i], new_dp);
      }
    }
    for (int i = 1; i <= m; i++) {
      a[i] = accumulate(dp[i].begin(), dp[i].end(), mint(0));
    }
    for (int i = m; i > 1; i--) {
      if (!is_prime[i]) {
        continue;
      }
      for (int j = 1; i * j <= m; j++) {
        a[j] -= a[i * j];
      }
    }
    cout << a[1] << '\n';
    return 0;
  }
  