human
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.
Solve the task in PYTHON3.
 ... What is a Python program to find it modulo 998 244 353?
assistant
#Here is Python program to find it modulo 998 244 353.

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]
                    cnts2[summ]=(cnts2[summ]+MOD)%MOD
            p2=cnts2.copy()
            for j in range(1,m2+1):
                p2[j]+=p2[j-1]
                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]
            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...