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;
  std::mt19937 rng(
      (int)std::chrono::steady_clock::now().time_since_epoch().count());
  long long cdiv(long long a, long long b) {
    return a / b + ((a ^ b) > 0 && a % b);
  }
  long long fdiv(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b);
  }
  long long gcd(long long a, long long b) {
    return (b == 0LL ? a : gcd(b, a % b));
  }
  long long exp(long long b, long long e, long long m) {
    b %= m;
    long long ans = 1;
    for (; e; b = b * b % m, e /= 2)
      if (e & 1) ans = ans * b % m;
    return ans;
  }
  void dbg_out() { cerr << "\n"; }
  template <typename Head, typename... Tail>
  void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
  }
  const int N = 100100;
  vector<int> pr;
  int mu[N];
  int mark[N];
  void crivo() {
    for (int i = 1; i < (N); ++i) {
      mu[i] = 1;
      mark[i] = 0;
    }
    for (int i = 2; i < (N); ++i) {
      if (!mark[i]) {
        pr.push_back(i);
        mu[i] = -1;
      }
      for (auto p : pr) {
        if (1ll * p * i >= N) break;
        mark[i * p] = 1;
        if (i % p == 0) {
          mu[i * p] = 0;
          break;
        } else
          mu[i * p] = -mu[i];
      }
    }
  }
  int l[N], r[N];
  long long dp[N], pre[N];
  const int M = 998244353;
  int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ;
    crivo();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < (n + 1); ++i) cin >> l[i] >> r[i];
    long long res = 0;
    for (int V = 1; V < (m + 1); ++V)
      if (mu[V] != 0) {
        int mx = m / V;
        for (int i = 0; i < (mx + 1); ++i) pre[i] = dp[i] = 0;
        dp[0] = 1;
        for (int i = 0; i < (mx + 1); ++i) pre[i] = 1;
        int bad = 0;
        for (int k = 1; k < (n + 1); ++k) {
          int L = (l[k] + V - 1) / V;
          int R = r[k] / V;
          if (R == 0 || L > R) {
            bad = 1;
            break;
          }
          for (int i = 0; i < (mx + 1); ++i) {
            if (i - L >= 0)
              dp[i] =
                  (M + pre[i - L] - (i - R - 1 >= 0 ? pre[i - R - 1] : 0)) % M;
            else
              dp[i] = 0;
          }
          for (int i = 0; i < (mx + 1); ++i) {
            pre[i] = dp[i] % M;
            if (i) pre[i] = (pre[i] + pre[i - 1]) % M;
          }
        }
        if (!bad) res += mu[V] * pre[mx] % M;
        res %= M;
        if (res < 0) res += M;
      }
    cout << res << "\n";
  }
  