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: 
  def naiveSolve():
      
      
      
      return
  
  from collections import Counter
  
  def main():
      
      n,m=readIntArr()
      l=[]
      r=[]
      for _ in range(n):
          ll,rr=readIntArr()
          l.append(ll)
          r.append(rr)
      
      def countWays(mult): # count the number of ways that gcd is a multiple of mult
          # compress everything by mult
          m2=m//mult
          cnts=[0]*(m2+1) # counts
          cnts[0]=1
          p=cnts.copy() # prefix sum
          for i in range(1,m2+1):
              p[i]+=p[i-1]
          # print('m2:{} cnts:{} p:{}'.format(m2,cnts,p))
          for i in range(n):
              lower=(l[i]+mult-1)//mult
              upper=r[i]//mult
              if lower>upper: # cnts will be all 0
                  return 0
              cnts2=[0]*(m2+1)
              for summ in range(m2+1):
                  prevUpper=min(summ-lower,m2+1)
                  prevLower=max(0,summ-upper)
                  # print('summ:{} prevU:{} prevL:{}'.format(summ,prevUpper,prevLower))
                  if prevLower<=prevUpper:
                      if prevLower==0:
                          cnts2[summ]=p[prevUpper]
                      else:
                          cnts2[summ]=p[prevUpper]-p[prevLower-1]
                      if cnts2[summ]<0:
                          cnts2[summ]+=MOD # smart mod
                      # cnts2[summ]=(cnts2[summ]+MOD)%MOD
              p2=cnts2.copy()
              for j in range(1,m2+1):
                  p2[j]+=p2[j-1]
                  if p2[j]>=MOD:
                      p2[j]-=MOD # smart mod
                  # p2[j]%=MOD
              cnts=cnts2
              p=p2
              # print('i:{} lower:{} upper:{} cnts:{} p:{}'.format(i,lower,upper,cnts,p))
          return p2[m2]
                      
          
      cnts=[-1]*(m+1) # cnts[gcd] = counts with gcd being gcd
      for mult in range(m,0,-1):
          nWays=countWays(mult)
          for mult2 in range(mult*2,m+1,mult):
              nWays-=cnts[mult2]
              if nWays<0:
                  nWays+=MOD
              # nWays=(nWays+MOD)%MOD
          cnts[mult]=nWays
      print(cnts[1])
      
      return
  
  
  import sys
  input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
  # input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.
  
  def oneLineArrayPrint(arr):
      print(' '.join([str(x) for x in arr]))
  def multiLineArrayPrint(arr):
      print('\n'.join([str(x) for x in arr]))
  def multiLineArrayOfArraysPrint(arr):
      print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
   
  def readIntArr():
      return [int(x) for x in input().split()]
  # def readFloatArr():
  #     return [float(x) for x in input().split()]
   
  def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
      dv=defaultValFactory;da=dimensionArr
      if len(da)==1:return [dv() for _ in range(da[0])]
      else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
   
  def queryInteractive(x):
      print('{}'.format(x))
      sys.stdout.flush()
      return int(input())
   
  def answerInteractive(ans):
      print('! {}'.format(ans))
      sys.stdout.flush()
   
  inf=float('inf')
  # MOD=10**9+7
  MOD=998244353
  
  from math import gcd,floor,ceil
  # from math import floor,ceil # for Python2
   
  for _abc in range(1):
      main()