#これでTLEしたら草ですねぇ！
class SegTree():
	def __init__(self, size):
		self.size = 1
		while self.size < size:
			self.size *= 2
		self.table = [set() for _ in range(2 * self.size - 1)]

n, m = map(int, input().split())
#m = int(input())
s = SegTree(m+1)
l = s.size
for i in range(1, m+1):
	for j in range(0, m+1, i):
		k = j+l-1
		s.table[k].add(i)
		while k > 0:
			k = (k-1) // 2
			s.table[k].add(i)
#print(s.table)
def query(a, b, k, l, r):
	if r <= a or b <= l:
		return set()
	elif a <= l and r <= b:
		return s.table[k]
	else:
		vl = query(a, b, k*2+1, l, (l+r)//2)
		vr = query(a, b, k*2+2, (l+r)//2, r)
		return vl | vr

for i in range(n):
	x, y = map(int, input().split())
	print(query(x, y+1, 0, 0, l))