#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;
}

### Prompt

Develop a solution in CPP to the problem described below:

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>
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;
}

```