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;
  const long long M = 998244353;
  vector<int> mu((int)1e5 + 1, 0);
  vector<int> primes;
  vector<int> isprime((int)1e5 + 1, 1);
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    mu[1] = 1;
    for (int i = 2; i < mu.size(); i++) {
      if (isprime[i]) {
        mu[i] = -1;
        primes.push_back(i);
      }
      for (auto j : primes) {
        if (j * i >= mu.size()) break;
        isprime[i * j] = 0;
        if (i % j != 0)
          mu[i * j] = mu[i] * mu[j];
        else {
          mu[i * j] = 0;
          break;
        }
      }
    }
    long long n, m;
    cin >> n >> m;
    vector<pair<int, int>> v(n + 1);
    long long cmax = 1e9;
    for (int i = 1; i < n + 1; i++) {
      cin >> v[i].first >> v[i].second;
      cmax = min(cmax, (long long)v[i].second);
    }
    long long ans = 0;
    for (int d = 1; d < cmax + 1; d++) {
      long long mm = m / d;
      long long dp[n + 1][mm + 1];
      memset(dp, 0, sizeof(dp));
      dp[0][0] = 1;
      for (int j = 1; j < mm + 1; j++) dp[0][j] = 1;
      for (int i = 1; i < n + 1; i++) {
        long long l = (v[i].first + d - 1) / d;
        long long r = (v[i].second) / d;
        for (int j = 1; j < mm + 1; j++) {
          if (j - r - 1 >= 0) dp[i][j] -= dp[i - 1][j - r - 1];
          if (j - l >= 0) dp[i][j] += dp[i - 1][j - l];
          if (j > 1) dp[i][j] += dp[i][j - 1];
          if (dp[i][j] < 0) {
            dp[i][j] += M;
            assert(dp[i][j] > 0);
          }
          dp[i][j] %= M;
        }
      }
      ans += ((long long)mu[d] * dp[n][mm]) % M;
      ans %= M;
    }
    if (ans < 0) ans += M;
    cout << ans;
  }
  