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 <class T>
  void _R(T &x) {
    cin >> x;
  }
  void _R(int &x) { scanf("%d", &x); }
  void _R(long long &x) { scanf("%lld", &x); }
  void _R(unsigned long long &x) { scanf("%llu", &x); }
  void _R(double &x) { scanf("%lf", &x); }
  void _R(char &x) { scanf(" %c", &x); }
  void _R(char *x) { scanf("%s", x); }
  void R() {}
  template <class T, class... U>
  void R(T &head, U &...tail) {
    _R(head);
    R(tail...);
  }
  template <class T>
  void _W(const T &x) {
    cout << x;
  }
  void _W(const int &x) { printf("%d", x); }
  void _W(const long long &x) { printf("%lld", x); }
  void _W(const double &x) { printf("%.16f", x); }
  void _W(const char &x) { putchar(x); }
  void _W(const char *x) { printf("%s", x); }
  template <class T, class U>
  void _W(const pair<T, U> &x) {
    _W(x.first);
    putchar(' ');
    _W(x.second);
  }
  template <class T>
  void _W(const vector<T> &x) {
    for (auto i = x.begin(); i != x.end(); _W(*i++))
      if (i != x.cbegin()) putchar(' ');
  }
  void W() {}
  template <class T, class... U>
  void W(const T &head, const U &...tail) {
    _W(head);
    putchar(sizeof...(tail) ? ' ' : '\n');
    W(tail...);
  }
  const int MOD = 998244353, mod = 998244353;
  long long qpow(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    assert(b >= 0);
    for (; b; b >>= 1) {
      if (b & 1) res = res * a % MOD;
      a = a * a % MOD;
    }
    return res;
  }
  const int MAXN = 4e5 + 10, MAXM = 2e6 + 10;
  const int INF = INT_MAX, SINF = 0x3f3f3f3f;
  const long long llINF = LLONG_MAX, SLINF = 0x3f3f3f3f3f3f3f3f;
  const int inv2 = (MOD + 1) / 2;
  const int Lim = 1 << 20;
  bool ispri[MAXM];
  int p[MAXN], mu[MAXM], phi[MAXM], pcnt;
  void get_pri(int n) {
    ispri[1] = mu[1] = phi[1] = 1;
    for (int i = 2; i <= n; i++) {
      if (!ispri[i]) p[++pcnt] = i, mu[i] = -1, phi[i] = i - 1;
      for (int j = 1; j <= pcnt && i * p[j] <= n; j++) {
        ispri[i * p[j]] = 1;
        if (i % p[j] == 0) {
          phi[i * p[j]] = p[j] * phi[i];
          break;
        }
        mu[i * p[j]] = -mu[i];
        phi[i * p[j]] = phi[i] * (p[j] - 1);
      }
    }
  }
  int n, m;
  int l[MAXN], r[MAXN];
  template <int _P>
  struct Modint {
    static constexpr int P = _P;
  
   private:
    int v;
  
   public:
    Modint() : v(0) {}
    Modint(long long _v) {
      v = _v % P;
      if (v < 0) v += P;
    }
    explicit operator int() const { return v; }
    explicit operator long long() const { return v; }
    explicit operator bool() const { return v > 0; }
    bool operator==(const Modint &o) const { return v == o.v; }
    bool operator!=(const Modint &o) const { return v != o.v; }
    Modint operator-() const { return Modint(v ? P - v : 0); }
    Modint operator+() const { return *this; }
    Modint &operator++() {
      v++;
      if (v == P) v = 0;
      return *this;
    }
    Modint &operator--() {
      if (v == 0) v = P;
      v--;
      return *this;
    }
    Modint operator++(int) {
      Modint r = *this;
      ++*this;
      return r;
    }
    Modint operator--(int) {
      Modint r = *this;
      --*this;
      return r;
    }
    Modint &operator+=(const Modint &o) {
      v += o.v;
      if (v >= P) v -= P;
      return *this;
    }
    Modint operator+(const Modint &o) const { return Modint(*this) += o; }
    Modint &operator-=(const Modint &o) {
      v -= o.v;
      if (v < 0) v += P;
      return *this;
    }
    Modint operator-(const Modint &o) const { return Modint(*this) -= o; }
    Modint &operator*=(const Modint &o) {
      v = (int)(((long long)v) * o.v % P);
      return *this;
    }
    Modint operator*(const Modint &o) const { return Modint(*this) *= o; }
    Modint &operator/=(const Modint &o) { return (*this) *= o.Inv(); }
    Modint operator/(const Modint &o) const { return Modint(*this) /= o; }
    Modint operator+(const long long &o) const { return (*this) + (Modint)o; }
    Modint operator-(const long long &o) const { return (*this) - (Modint)o; }
    Modint operator*(const long long &o) const { return (*this) * (Modint)o; }
    Modint operator^(long long o) const {
      Modint r = 1, t = v;
      while (o) {
        if (o & 1) r *= t;
        t *= t;
        o >>= 1;
      }
      return r;
    }
    Modint operator~() { return (*this) ^ (P - 2); }
    Modint Inv() const { return (*this) ^ (P - 2); }
  };
  using mi = Modint<MOD>;
  template <int P>
  void _W(Modint<P> x) {
    printf("%d", (int)x);
  }
  template <int P>
  void _R(Modint<P> &x) {
    long long t;
    scanf("%lld", &t);
    x = t;
  }
  mi dp[MAXN], sum[MAXN], ans;
  void solve() {
    R(n, m);
    for (int i = 1; i <= n; i++) R(l[i], r[i]);
    for (int d = 1; d <= m; d++) {
      int M = m / d;
      for (int i = 0; i <= M; i++) dp[i] = 0, sum[i] = 1;
      dp[0] = 1;
      for (int i = 1; i <= n; i++) {
        int L = (l[i] + d - 1) / d, R = r[i] / d;
        for (int j = 0; j <= M; j++) dp[j] = 0;
        for (int j = 0; j <= M; j++) {
          int tl = j - R - 1, tr = j - L;
          if (tr >= 0) dp[j] += sum[tr];
          if (tl >= 0) dp[j] -= sum[tl];
        }
        for (int j = 0; j <= M; j++) {
          sum[j] = dp[j];
          if (j) sum[j] += sum[j - 1];
        }
      }
      ans += ((mi)mu[d]) * sum[M];
    }
    W(ans);
  }
  int main() {
    get_pri(200000);
    int T = 1;
    for (int kase = 1; kase <= T; kase++) {
      solve();
    }
    return 0;
  }
  