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: import sys
  import os
  from io import BytesIO
  from math import ceil
  
  if sys.version_info[0] < 3:
      sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
  
  f = sys.stdin
  
  line = lambda: f.readline().strip('\r\n').split()
  
  def write(w):
      sys.stdout.write(w)
      sys.stdout.write("\n")
  
  def solve():
      
      ways = [0] * (M+1)
      
      for d in range(M,0,-1): 
          m = M//d
          dp = [0 for j in range(m+1)]
          dp[0] = 1
          pref = [0 for _ in range(m+1)]
          f = True
          
          for i in range(1,N+1):
              l = D[i-1][0]
              r = D[i-1][1]
              l = (l+d-1) // d
              r //= d
              
              if l>r:
                  f = False
                  break
              
              pref[0] = dp[0]
              for j in range(1,m+1):
                  pref[j] = (pref[j-1] + dp[j]) % MOD
              
              for j in range(1,m+1):
                  a = b = 0
                  if j >= l:
                      a = pref[j-l]
                  if j >= r+1:
                      b = pref[j-r-1]
                  dp[j] = a - b
                  dp[j] %= MOD
              dp[0] = 0
          
          v = sum(dp[j] for j in range(1,m+1))
          if f:
              ways[d] = v
              for j in range(2*d,M+1,d):
                  ways[d] -= ways[j]
                  ways[d] %= MOD
      
      return str(ways[1]%MOD)
  
  MOD = 998244353
  T = 1
  for test in range(1,T+1):
      N,M = map(int,line())
      D = []
      for _ in range(N):
          l,r = map(int,line())
          D.append((l,r))
      
      write(solve())
      
  f.close()