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

### Prompt

Create a solution in cpp for 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;
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;
}

```