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.

Difficulty: HARD
Tags: Combinatorics

Number theory

Dynamic programming

Mathematics

Polynomials and generating functions
Skill types: Dynamic programming

Starter code:

Solutions:
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):
		m2 = m // mult
		cnts = [0] * (m2 + 1)
		cnts[0] = 1
		p = cnts.copy()
		for i in range(1, m2 + 1):
			p[i] += p[i - 1]
		for i in range(n):
			lower = (l[i] + mult - 1) // mult
			upper = r[i] // mult
			if lower > upper:
				return 0
			cnts2 = [0] * (m2 + 1)
			for summ in range(m2 + 1):
				prevUpper = min(summ - lower, m2 + 1)
				prevLower = max(0, summ - upper)
				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
			p2 = cnts2.copy()
			for j in range(1, m2 + 1):
				p2[j] += p2[j - 1]
				if p2[j] >= MOD:
					p2[j] -= MOD
			cnts = cnts2
			p = p2
		return p2[m2]
	cnts = [-1] * (m + 1)
	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
		cnts[mult] = nWays
	print(cnts[1])
	return
import sys
input = sys.stdin.buffer.readline

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 makeArr(defaultValFactory, dimensionArr):
	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 = 998244353
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys
input = sys.stdin.buffer.readline
mod = 998244353
(n, m) = map(int, input().split())
primes = [0] * (m + 1)
prime = [1] * (m + 1)
for i in range(2, m + 1):
	if prime[i]:
		for j in range(2 * i, m + 1, i):
			prime[j] = 0
			primes[j] += 1
for i in range(2, m + 1):
	if prime[i]:
		for j in range(i * i, m + 1, i * i):
			primes[j] = -1
ranges = [list(map(int, input().split())) for i in range(n)]
ways_gcd = [0] * (m + 1)
for gcd in range(1, m + 1):
	converted_ranges = [[(ranges[i][0] + gcd - 1) // gcd, ranges[i][1] // gcd] for i in range(n)]
	dp1 = [0] * (m // gcd + 1)
	dp1[0] = 1
	dp2 = [0] * (m // gcd + 1)
	for i in range(n):
		if converted_ranges[i][0] > converted_ranges[i][1]:
			(dp1, dp2) = (dp2, dp1)
			break
		(l, r) = converted_ranges[i]
		for j in range(len(dp2) - l):
			dp2[j + l] = (dp2[j + l] + dp1[j]) % mod
			if j + r + 1 < len(dp2):
				dp2[j + r + 1] = (dp2[j + r + 1] - dp1[j] + mod) % mod
		for i in range(1, len(dp2)):
			dp2[i] = (dp2[i] + dp2[i - 1]) % mod
		(dp1, dp2) = (dp2, dp1)
		dp2 = [0] * len(dp2)
	ways_gcd[gcd] = sum(dp1) % mod
ans = ways_gcd[1]
for i in range(2, m + 1):
	if primes[i] >= 2 or prime[i]:
		if prime[i] or primes[i] & 1:
			ans = (ans - ways_gcd[i] + mod) % mod
		else:
			ans = (ans + ways_gcd[i]) % mod
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	(n, m) = map(int, input().split())
	intervals = []
	for i in range(n):
		(x, y) = map(int, input().split())
		intervals += [[x, y]]
	mod = 998244353
	ways = [0] * 100001
	for i in range(100000, 0, -1):
		bound = m // i
		if not bound:
			continue
		dp = [0] * (bound + 1)
		pre = [1] * (bound + 2)
		pre[0] = 0
		dp[0] = 1
		t = 0
		for (x, y) in intervals:
			(left, right) = ((x + i - 1) // i, (y + i) // i)
			for v in range(bound, -1, -1):
				dp[v] = 0
				(l, r) = (v - (right - 1), v - left)
				if left == right or r < 0:
					continue
				dp[v] = (pre[r + 1] - pre[max(0, l)]) % mod
			for j in range(1, bound + 2):
				pre[j] = (pre[j - 1] + dp[j - 1]) % mod
		ways[i] = pre[-1]
		for j in range(2 * i, 100001, i):
			ways[i] -= ways[j]
		ways[i] %= mod
	print(ways[1] % mod)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
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(ans)


import sys
import math
from collections import deque, Counter
from sys import stdin
int1 = lambda x: int(x) - 1
inp = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
mi1 = lambda : map(int1, input().split())
li1 = lambda : list(mi1())
mis = lambda : map(str, input().split())
lis = lambda : list(mis())
stinput = lambda : stdin.readline()[:-1]
stinp = lambda : int(stinput())
stmi = lambda : map(int, stdin.readline().split())
stli = lambda : list(stmi())
stmi1 = lambda : map(int1, stdin.readline().split())
stli1 = lambda : list(stmi1())
stmis = lambda : stdin.readline()[:-1]
pr = print
from collections import defaultdict
mod = 10 ** 9 + 7
Mod = 998244353
INF = 10 ** 18
ans = 0
(n, m) = mi()
x = []
for i in range(n):
	(a, b) = mi()
	x.append((a, b))

def f(k):
	dp = [0] * (m // k + 1)
	t = m // k + 1
	dp[0] = 1
	for (a, b) in x:
		dp2 = [0] * t
		c = (a + k - 1) // k
		d = b // k
		cnt = 0
		for i in range(c, t):
			cnt += dp[i - c]
			if i > d:
				cnt -= dp[i - d - 1]
			cnt %= Mod
			dp2[i] = cnt
		dp = dp2.copy()
	return sum(dp) % Mod
tmp = [0] * (m + 1)
for i in range(m, 0, -1):
	t = f(i)
	j = 2 * i
	while j <= m:
		t -= tmp[j]
		j += i
	tmp[i] = t % Mod
print(tmp[1] % Mod)


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)


import math
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
p = 998244353
(n, m) = map(int, input().split())
c = []
for i in range(n):
	b = list(map(int, input().split()))
	c.append(b)
val = [0 for i in range(m + 1)]
for i in range(m, 0, -1):
	s = m // i
	ans = 0
	dp = [0 for j in range(s + 1)]
	pre = [1 for i in range(s + 1)]
	pre[0] = 1
	fl = 1
	for pos in range(n):
		(l, r) = (math.ceil(c[pos][0] / i), c[pos][1] // i)
		if l > r:
			fl = 0
			break
		for j in range(l, s + 1):
			le = j - r
			re = j - l
			if le < 1:
				dp[j] = (dp[j] + pre[re]) % p
			else:
				dp[j] = (dp[j] + pre[re] - pre[le - 1]) % p
		pre[0] = 0
		dp[0] = 0
		for j in range(1, s + 1):
			pre[j] = (dp[j] + pre[j - 1]) % p
			dp[j] = 0
	if fl:
		curr = pre[s]
		tot = 0
		for j in range(2 * i, m + 1, i):
			tot = (tot + val[j]) % p
		val[i] = (curr - tot) % p
	else:
		val[i] = 0
print(val[1] % p)


import math
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
mod = 998244353
lr = [list(map(int, input().split())) for _ in range(n)]
ans = 0
s = [0] * (m + 1)
s[1] = 1
for j in range(1, m + 1):
	m0 = m // j
	dpsum = [1] * (m0 + 2)
	dpsum[0] = 0
	dp = [0] * (m0 + 1)
	ok = 1
	s0 = 0
	for (l, r) in lr:
		(l0, r0) = (int(math.ceil(l / j)), r // j)
		if l0 > r0:
			ok = 0
			break
		l0 -= 1
		for i in range(m0 + 1):
			dp[i] = dpsum[max(0, i - l0)] - dpsum[max(0, i - r0)]
			dp[i] %= mod
		for i in range(m0 + 1):
			dpsum[i + 1] = dp[i] + dpsum[i]
			dpsum[i + 1] %= mod
	if ok:
		sj = s[j]
		ss = 0
		for i in range(m0 + 1):
			ss += dp[i]
			ss %= mod
		ans += sj * ss % mod
		ans %= mod
		for k in range(2 * j, m + 1, j):
			s[k] -= sj
print(ans)


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
inf = 10 ** 16
md = 998244353
(n, M) = LI()
lr = LLI(n)

def doDP(g):
	m = M // g
	dp = [0] * (m + 3)
	dp[0] = 1
	for (i, (l, r)) in enumerate(lr):
		(l, r) = ((l + g - 1) // g, r // g)
		ndp = [0] * (m + 3)
		for j in range(m):
			pre = dp[j]
			if pre == 0:
				continue
			nl = j + l
			if nl > m:
				break
			nr = min(j + r + 1, m + 1)
			ndp[nl] = (ndp[nl] + pre) % md
			ndp[nr] = (ndp[nr] - pre) % md
		for j in range(m):
			ndp[j + 1] = (ndp[j + 1] + ndp[j]) % md
		dp = ndp
	res = 0
	for v in dp[1:m + 1]:
		res = (res + v) % md
	return res
ans = [0]
for g in range(1, M + 1):
	ans.append(doDP(g))
for i in range(M - 1, 0, -1):
	for j in range(i + i, M + 1, i):
		ans[i] -= ans[j]
	ans[i] %= md
print(ans[1])