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>
  const int mod = 998244353;
  struct modint {
    int val;
    inline void check() {
      val >= mod ? val %= mod : true;
      val < 0 ? (val %= mod) += mod : true;
      return;
    }
    modint(int v = 0) : val(v) { check(); }
    inline modint &operator=(int v) { return val = v, *this; }
    inline modint &operator+=(modint rhs) {
      return val = val + rhs.val > mod ? val + rhs.val - mod : val + rhs.val,
             *this;
    }
    inline modint &operator-=(modint rhs) {
      return val = val - rhs.val < 0 ? val - rhs.val + mod : val - rhs.val, *this;
    }
    inline modint &operator*=(modint rhs) {
      return val = 1ll * val * rhs.val % mod, *this;
    }
    inline friend modint operator+(const modint &lhs, const modint &rhs) {
      return modint(lhs) += rhs;
    }
    inline friend modint operator-(const modint &lhs, const modint &rhs) {
      return modint(lhs) -= rhs;
    }
    inline friend modint operator*(const modint &lhs, const modint &rhs) {
      return modint(lhs) *= rhs;
    }
    inline friend bool operator==(const modint &lhs, const modint &rhs) {
      return lhs.val == rhs.val;
    }
    inline friend bool operator!=(const modint &lhs, const modint &rhs) {
      return lhs.val != rhs.val;
    }
    inline friend bool operator>(const modint &lhs, const modint &rhs) {
      return lhs.val > rhs.val;
    }
    inline friend bool operator<(const modint &lhs, const modint &rhs) {
      return lhs.val < rhs.val;
    }
    inline friend bool operator>=(const modint &lhs, const modint &rhs) {
      return lhs.val >= rhs.val;
    }
    inline friend bool operator<=(const modint &lhs, const modint &rhs) {
      return lhs.val <= rhs.val;
    }
    inline modint &operator++() {
      ++val;
      if (val == mod) val = 0;
      return *this;
    }
    inline modint &operator--() {
      if (val == 0) val = mod;
      --val;
      return *this;
    }
    inline modint operator++(int) {
      modint ret = *this;
      ++*this;
      return ret;
    }
    inline modint operator--(int) {
      modint ret = *this;
      --*this;
      return ret;
    }
    inline modint operator+() const { return *this; }
    inline modint operator-() const { return modint() - *this; }
  };
  namespace fastIO {
  const int maxc = 1 << 23;
  char ibuf[maxc], *__p1 = ibuf, *__p2 = ibuf;
  inline char getchar() {
    return __p1 == __p2 && (__p2 = (__p1 = ibuf) + fread(ibuf, 1, maxc, stdin),
                            __p1 == __p2)
               ? EOF
               : *__p1++;
  }
  template <typename T>
  void read(T &n) {
    int x = 0;
    n = 0;
    char c = getchar();
    while (!isdigit(c)) x |= (c == '-'), c = getchar();
    while (isdigit(c)) n = n * 10 + c - '0', c = getchar();
    n = x ? -n : n;
  }
  char obuf[maxc], *__pO = obuf;
  inline void putchar(char c) { *__pO++ = c; }
  template <typename T>
  void print(T x) {
    if (x < 0)
      putchar('-'), print(-x);
    else {
      if (x > 9) print(x / 10);
      putchar(x % 10 + '0');
    }
    return;
  }
  void print(modint x) { print(x.val); }
  void output() { fwrite(obuf, __pO - obuf, 1, stdout); }
  }  // namespace fastIO
  using namespace fastIO;
  const int maxn = 55, maxm = 1e5 + 5;
  int n, m, L[maxn], R[maxn], l[maxn], r[maxn];
  int p[maxm], vis[maxm], mu[maxm], cntp;
  modint f[maxm], sum[maxm];
  void init() {
    static const int N = 1e5;
    mu[1] = 1;
    for (int i = (2); i <= (N); ++i) {
      if (!vis[i]) p[++cntp] = i, mu[i] = -1;
      for (int j = 1; j <= cntp && i * p[j] <= N; ++j) {
        vis[i * p[j]] = 1;
        if (i % p[j] == 0) {
          mu[i * p[j]] = 0;
          break;
        }
        mu[i * p[j]] = -mu[i];
      }
    }
    return;
  }
  int main() {
    init();
    read(n), read(m);
    for (int i = (1); i <= (n); ++i) read(L[i]), read(R[i]);
    modint ans = 0;
    for (int d = (1); d <= (m); ++d) {
      if (mu[d] == 0) continue;
      for (int j = (0); j <= (m / d); ++j) sum[j] = 1;
      for (int i = (1); i <= (n); ++i) {
        l[i] = (L[i] + d - 1) / d, r[i] = R[i] / d;
        for (int j = (1); j <= (m / d); ++j) f[j] = 0;
        for (int j = (l[i]); j <= (m / d); ++j) {
          f[j] = sum[j - l[i]];
          if (j - r[i] - 1 >= 0) f[j] -= sum[j - r[i] - 1];
        }
        sum[0] = 0;
        for (int j = (1); j <= (m / d); ++j) sum[j] = f[j] + sum[j - 1];
      }
      ans += sum[m / d] * mu[d];
    }
    print(ans);
    return output(), 0;
  }
  