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: #!/usr/bin/env python3
  # from typing import *
  
  import sys
  import io
  import math
  import collections
  import decimal
  import itertools
  import bisect
  import heapq
  
  
  def input():
      return sys.stdin.readline()[:-1]
  
  
  # sys.setrecursionlimit(1000000)
  
  # _INPUT = """2 4
  # 1 3
  # 1 2
  # """
  # sys.stdin = io.StringIO(_INPUT)
  
  INF = 10**10
  
  MOD = 998244353
  
  
  def solve(d):
      M1 = M//d
  
      dp = [0] * (M1+1)
      dp[0] = 1
      for i in range(N):
          s = [0]
          for v in dp:
              s.append((s[-1] + v) % MOD)
          l, r = T[i]
          l1, r1 = math.ceil(l/d), r//d
          for m in range(M1+1):
              l2 = max(m-r1, 0)
              r2 = max(m-l1+1, 0)
              dp[m] = (s[r2] - s[l2]) % MOD
  
      return sum(dp[1:]) % MOD
  
  
  def Mobius(n):
      s = set()
      while n > 1:
          if D[n] in s:
              return 0
          s.add(D[n])
          n //= D[n]
      if len(s) % 2 == 0:
          return 1
      else:
          return -1
  
  N, M = map(int, input().split())
  T = []
  for _ in range(N):
      l, r = map(int, input().split())
      T.append((l, r))
  
  A_MAX = M
  D = [0] * (A_MAX + 1)
  for i in range(2, A_MAX + 1):
      if D[i] == 0:
          D[i] = i
          n = i * i
          while n <= A_MAX:
              D[n] = i
              n += i
  
  Table = [0] * (M+1)
  ans = 0
  for d in range(1, M//N+1):
      mo = Mobius(d)
      if mo == 0:
          continue
      v = solve(d)
      ans = (ans + mo * v) % MOD
      # print(d, v, n)
  print(ans)