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
  input=sys.stdin.readline
  
  max_n=10**5+1
  spf=[i for i in range(max_n)]
  prime=[True for i in range(max_n)]
  mobius=[0 for i in range(max_n)]
  prime[0]=prime[1]=False
  mobius[1]=1
  primes=[]
  for i in range(2,max_n):
      if(prime[i]):
          spf[i]=i
          mobius[i]=-1
          primes.append(i)
      for j in primes:
          prod=j*i
          if(j>spf[i] or prod>=max_n):
              break
          spf[prod]=j
          prime[prod]=False
          if(spf[i]==j):
              mobius[prod]=0
          else:
              mobius[prod]=-mobius[i]
  
  mod=998244353
  n,m=map(int,input().split())
  lower=[]
  upper=[]
  for i in range(n):
      l,r=map(int,input().split())
      lower.append(l)
      upper.append(r)
      
  def calc(low,high,n,m):
      if(n>m):
          return(0)
      dp=[[0 for j in range(m+1)] for i in range(n+1)]
      dp_pref=[[0 for j in range(m+1)] for i in range(n+1)]
      for j in range(low[0],m+1):
          if(j<=high[0]):
              dp[1][j]=1
          dp_pref[1][j]=dp[1][j]+dp_pref[1][j-1]
      for i in range(2,n+1):
          for j in range(1,m+1):
              dp[i][j]=(dp_pref[i-1][max(j-low[i-1],0)]-dp_pref[i-1][max(j-high[i-1]-1,0)])%mod
              dp_pref[i][j]=(dp[i][j]+dp_pref[i][j-1])%mod
      return(sum(dp[n])%mod)
  
  ans=calc(lower,upper,n,m)
  for i in range(2,m):
      low=[]
      high=[]
      for k in range(n):
          low.append((lower[k]+i-1)//i)
          high.append(upper[k]//i)
      val=calc(low,high,n,m//i)
      ans=(ans+mobius[i]*val)%mod
  print(ans)
          
          
          
  
      
      
  
      
  