#include <bits/stdc++.h>
using namespace std;
long long int modInverse(long long int a, long long int m) {
  long long int m0 = m;
  long long int y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long int q = a / m;
    long long int t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
void solve() {
  long long int n, m;
  cin >> n >> m;
  long long int mod = 998244353;
  long long int dp[m + 1], pp[m + 1];
  for (int j = 0; j <= m; j++) {
    dp[j] = 0;
  }
  dp[0] = 1;
  long long int A[n], B[n];
  for (long long int i = 0; i < n; i++) {
    long long int l, r;
    cin >> l >> r;
    A[i] = l;
    B[i] = r;
    for (int j = 0; j <= m; j++) {
      pp[j] = 0;
    }
    long long int sum = 0;
    for (int j = l; j <= m; j++) {
      sum += dp[j - l];
      sum %= mod;
      if (j - r - 1 >= 0) {
        sum -= dp[j - r - 1];
      }
      sum %= mod;
      sum += mod;
      sum %= mod;
      pp[j] = sum;
    }
    for (int j = 0; j <= m; j++) {
      dp[j] = pp[j];
    }
  }
  for (int j = 2; j <= m; j++) {
    long long int flag = 1, val = 0;
    long long int k = j;
    for (int l = 2; l * l <= k; l++) {
      int gg = 0;
      while (k % l == 0) {
        k /= l;
        gg++;
        if (gg > 1) {
          flag = 0;
          break;
        }
      }
      val += gg;
      if (flag == 0) {
        break;
      }
    }
    if (k > 1) {
      val++;
    }
    if (flag == 0) {
      continue;
    }
    long long int m1 = m / j, l1, r1;
    long long int dp1[m1];
    long long int pp1[m1];
    for (int i = 0; i <= m1; i++) {
      dp1[i] = 0;
    }
    dp1[0] = 1;
    for (int y = 0; y < n; y++) {
      l1 = A[y];
      l1 = (l1 + j - 1) / j;
      r1 = B[y];
      r1 /= j;
      for (int i = 0; i <= m1; i++) {
        pp1[i] = 0;
      }
      long long int sum = 0;
      for (int i = l1; i <= m1; i++) {
        sum += dp1[i - l1];
        sum %= mod;
        if (i - r1 - 1 >= 0) {
          sum -= dp1[i - r1 - 1];
        }
        sum %= mod;
        sum += mod;
        sum %= mod;
        pp1[i] = sum;
      }
      for (int i = 0; i <= m1; i++) {
        dp1[i] = pp1[i];
        if (y == n - 1) {
          if (val % 2 == 1) {
            dp[i] -= dp1[i];
            dp[i] %= mod;
            dp[i] += mod;
            dp[i] %= mod;
          } else {
            dp[i] += dp1[i];
            dp[i] %= mod;
          }
        }
      }
    }
  }
  long long int ans = 0;
  for (int i = 1; i <= m; i++) {
    ans += dp[i];
    ans %= mod;
  }
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  while (t--) solve();
}

### Prompt

Your task is to create a cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long int modInverse(long long int a, long long int m) {
  long long int m0 = m;
  long long int y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long int q = a / m;
    long long int t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
void solve() {
  long long int n, m;
  cin >> n >> m;
  long long int mod = 998244353;
  long long int dp[m + 1], pp[m + 1];
  for (int j = 0; j <= m; j++) {
    dp[j] = 0;
  }
  dp[0] = 1;
  long long int A[n], B[n];
  for (long long int i = 0; i < n; i++) {
    long long int l, r;
    cin >> l >> r;
    A[i] = l;
    B[i] = r;
    for (int j = 0; j <= m; j++) {
      pp[j] = 0;
    }
    long long int sum = 0;
    for (int j = l; j <= m; j++) {
      sum += dp[j - l];
      sum %= mod;
      if (j - r - 1 >= 0) {
        sum -= dp[j - r - 1];
      }
      sum %= mod;
      sum += mod;
      sum %= mod;
      pp[j] = sum;
    }
    for (int j = 0; j <= m; j++) {
      dp[j] = pp[j];
    }
  }
  for (int j = 2; j <= m; j++) {
    long long int flag = 1, val = 0;
    long long int k = j;
    for (int l = 2; l * l <= k; l++) {
      int gg = 0;
      while (k % l == 0) {
        k /= l;
        gg++;
        if (gg > 1) {
          flag = 0;
          break;
        }
      }
      val += gg;
      if (flag == 0) {
        break;
      }
    }
    if (k > 1) {
      val++;
    }
    if (flag == 0) {
      continue;
    }
    long long int m1 = m / j, l1, r1;
    long long int dp1[m1];
    long long int pp1[m1];
    for (int i = 0; i <= m1; i++) {
      dp1[i] = 0;
    }
    dp1[0] = 1;
    for (int y = 0; y < n; y++) {
      l1 = A[y];
      l1 = (l1 + j - 1) / j;
      r1 = B[y];
      r1 /= j;
      for (int i = 0; i <= m1; i++) {
        pp1[i] = 0;
      }
      long long int sum = 0;
      for (int i = l1; i <= m1; i++) {
        sum += dp1[i - l1];
        sum %= mod;
        if (i - r1 - 1 >= 0) {
          sum -= dp1[i - r1 - 1];
        }
        sum %= mod;
        sum += mod;
        sum %= mod;
        pp1[i] = sum;
      }
      for (int i = 0; i <= m1; i++) {
        dp1[i] = pp1[i];
        if (y == n - 1) {
          if (val % 2 == 1) {
            dp[i] -= dp1[i];
            dp[i] %= mod;
            dp[i] += mod;
            dp[i] %= mod;
          } else {
            dp[i] += dp1[i];
            dp[i] %= mod;
          }
        }
      }
    }
  }
  long long int ans = 0;
  for (int i = 1; i <= m; i++) {
    ans += dp[i];
    ans %= mod;
  }
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  while (t--) solve();
}

```