Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Given integers $N$ and $M$, find the number of ordered pairs $(a, b)$ such that $1 ≤ a < b ≤ N$ and $((M\ \mathrm{mod}\ a)\ \mathrm{mod}\ b) = ((M\ \mathrm{mod}\ b)\ \mathrm{mod}\ a)$.

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
The only line of each test case contains two integers $N$, $M$. 

------ Output ------
For each testcase, output in a single line the answer to the problem.

------ Constraints  ------
$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{6}$
$1 ≤ M ≤ 5\cdot 10^{5}$
The sum of $N$ over all test cases does not exceed $10^{6}$.

Note: Multiplier for JAVA for this problem is reduced to $1.25$ instead of usual $2$.

------ Subtasks ------
Subtask #1 (10 points): 
$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{3}$
$1 ≤ M ≤ 10^{5}$

Subtask #2 (40 points): 
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
The sum of $N$ over all test cases does not exceed $10^{6}$.

Subtask #3 (50 points): Original Constraints

----- Sample Input 1 ------ 
3

3 5

3 6

3 10
----- Sample Output 1 ------ 
2

3

2
----- explanation 1 ------ 
Test Case $1$: There are $2$ valid pairs satisfying the conditions. These are:
- $(1, 2)$: $(1 ≤ 1 < 2 ≤ N)$. Given $M = 5$, $((5 \%1) \%2) = (0\%2) = 0$. Also, $((5 \%2) \%1) = (1\%1) = 0$.
- $(1, 3)$: $(1 ≤ 1 < 3 ≤ N)$. Given $M = 5$, $((5 \%1) \%3) = (0\%3) = 0$. Also, $((5 \%3) \%1) = (2\%1) = 0$.

Test Case $2$: There are $3$ valid pairs satisfying the conditions. These are:
- $(1, 2)$: $(1 ≤ 1 < 2 ≤ N)$. Given $M = 6$, $((6 \%1) \%2) = (0\%2) = 0$. Also, $((6 \%2) \%1) = (0\%1) = 0$.
- $(1, 3)$: $(1 ≤ 1 < 3 ≤ N)$. Given $M = 6$, $((6 \%1) \%3) = (0\%3) = 0$. Also, $((6 \%3) \%1) = (0\%1) = 0$.
- $(2, 3)$: $(1 ≤ 2 < 3 ≤ N)$. Given $M = 6$, $((6 \%2) \%3) = (0\%3) = 0$. Also, $((6 \%3) \%2) = (0\%2) = 0$.

Test Case $3$: There are $2$ valid pairs satisfying the conditions. These are:
- $(1, 2)$: $(1 ≤ 1 < 2 ≤ N)$. Given $M = 10$, $((10 \%1) \%2) = (0\%2) = 0$. Also, $((10 \%2) \%1) = (0\%1) = 0$.
- $(1, 3)$: $(1 ≤ 1 < 3 ≤ N)$. Given $M = 10$, $((10 \%1) \%3) = (0\%3) = 0$. Also, $((10 \%3) \%1) = (1\%1) = 0$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Sorting

Mathematics

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
t = int(input())
for a in range(t):
	(n, m) = map(int, input().split())
	l = [1] * (n + 1)
	k = 0
	for i in range(2, n + 1):
		a = m % i
		k += l[a]
		for j in range(a, n, i):
			l[j] += 1
	print(k)


def solve(n, m):
	va = 0
	arr = [1 for i in range(n + 1)]
	for i in range(2, n + 1):
		a = m % i
		va += arr[a]
		for j in range(a, n + 1, i):
			arr[j] += 1
	return va
for i in range(int(input())):
	(n, m) = map(int, input().split())
	print(solve(n, m))


def divisor(n):
	ans = [[1] for i in range(n + 1)]
	ans[0].pop()
	for i in range(2, n + 1):
		for j in range(i, n + 1, i):
			ans[j].append(i)
	return ans

def count(n, p, div):
	if n >= len(div):
		return 0
	size = len(div[n])
	(st, en) = (0, size - 1)
	check = 0
	while st <= en:
		mid = (st + en) // 2
		temp = div[n][mid]
		if temp == p:
			check = mid - 1
			break
		elif temp > p:
			en = mid - 1
		elif temp < p:
			check = mid
			st = mid + 1
	return check
t = int(input())
div = divisor(6 * 10 ** 5)
for _ in range(t):
	(n, m) = map(int, input().split())
	ans = 0
	for i in range(2, n + 1):
		temp = m // i * i
		if temp == 0:
			ans += i - 1
			continue
		c = count(temp, i, div) + 1
		ans += c
	print(ans)


import sys
input = sys.stdin.readline
T = int(input())
for j in range(T):
	(N, M) = map(int, input().split())
	result = 0
	arr = [1] * (N + 1)
	for i in range(2, N + 1):
		x = M % i
		result += arr[x]
		for j in range(x, N + 1, i):
			arr[j] += 1
	print(result)


T = int(input())
for j in range(T):
	(N, M) = map(int, input().split())
	result = 0
	arr = [1] * (N + 1)
	for i in range(2, N + 1):
		x = M % i
		result += arr[x]
		for j in range(x, N + 1, i):
			arr[j] += 1
	print(result)


from bisect import bisect_left
num = 500005
val = [[] for i in range(500005)]

def cal():
	for i in range(1, num):
		for j in range(i, num, i):
			val[j].append(i)
cal()
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	res = 0
	for b in range(2, n + 1):
		x = m - m % b
		if x:
			res += bisect_left(val[x], b)
		else:
			res += b - 1
	print(res)


try:

	def fun(n, m):
		a = 0
		L = [1 for i in range(n + 1)]
		for i in range(2, n + 1):
			x = m % i
			a += L[x]
			for j in range(x, n + 1, i):
				L[j] += 1
		return a
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		print(fun(n, m))
except:
	pass


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	c = 0
	me = [1] * (n + 1)
	for i in range(2, n + 1):
		x = m % i
		c = c + me[x]
		for j in range(x, n + 1, i):
			me[j] += 1
	print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	me = [1 for _ in range(n + 1)]
	counter = 0
	for i in range(2, n + 1):
		a = m % i
		counter += me[a]
		for j in range(a, n + 1, i):
			me[j] += 1
	print(counter)


MAX_M = 5 * 10 ** 5
factors = [[] for i in range(MAX_M + 1)]
for i in range(1, MAX_M + 1):
	for j in range(i, MAX_M + 1, i):
		factors[j].append(i)

def lowerBound(b, T):
	(left, right) = (0, len(factors[T]) - 1)
	while left < right:
		mid = (left + right) // 2
		if factors[T][mid] >= b:
			right = mid
		else:
			left = mid + 1
	return left
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	ans = 0
	for b in range(1, N + 1):
		x = M - M % b
		k = lowerBound(b, x) if b <= x else b - 1
		ans += k
	print(ans)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	s = 0
	ar = [1] * (N + 1)
	for i in range(2, N + 1):
		a = M % i
		s += ar[a]
		for j in range(a, N + 1, i):
			ar[j] += 1
	print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [1] * (n + 1)
	var = 0
	for i in range(2, n + 1):
		a = m % i
		var += arr[a]
		j = a
		while j <= n:
			arr[j] += 1
			j += i
	print(var)


t = int(input())
for _ in range(t):
	s = [int(x) for x in input().split()]
	(n, m) = (s[0], s[1])
	l = [1] * (n + 1)
	ans = 0
	for i in range(2, n + 1):
		a = m % i
		ans += l[a]
		for j in range(a, n + 1, i):
			l[j] += 1
	print(ans)


try:
	t = int(input())
	while t:
		(n, m) = map(int, input().split())
		l = [1] * (n + 1)
		ans = 0
		for i in range(2, n + 1):
			a = m % i
			ans += l[a]
			for j in range(a, n + 1, i):
				l[j] += 1
		print(ans)
except:
	pass


M = int(500000.0 + 5)
divisors = [[] for i in range(0, M + 1)]

def findDivisiors():
	for i in range(1, M + 1):
		for j in range(i, M + 1, i):
			divisors[j].append(i)

def binarySearch(numbers, start, end, num):
	if start <= end:
		mid = (start + end) // 2
		if numbers[mid] == num:
			return mid
		if num < numbers[mid]:
			return binarySearch(numbers, start, mid - 1, num)
		else:
			return binarySearch(numbers, mid + 1, end, num)
	return -1
t = int(input())
findDivisiors()
for i in range(t):
	(n, m) = map(int, input().split())
	count = 0
	for b in range(2, n + 1):
		x = m - m % b
		if x > 0:
			count += binarySearch(divisors[x], 0, len(divisors[x]) - 1, b)
		else:
			count += b - 1
	print(count)


test = int(input())
mex = 500001
div = [[] for _ in range(mex)]
for i in range(1, mex):
	for j in range(i, mex, i):
		div[j].append(i)
for i in range(test):
	fans = 0
	(n, m) = map(int, input().split())
	mx = min(n, m)
	for b in range(2, mx + 1):
		amul = m - m % b
		(s, e) = (0, len(div[amul]) - 1)
		ans = -1
		while s <= e:
			md = (s + e) // 2
			if div[amul][md] < b:
				ans = md
				s = md + 1
			else:
				e = md - 1
		fans += ans + 1
	for b in range(mx + 1, n + 1):
		fans += b - 1
	print(fans)


from collections import defaultdict
divs = defaultdict(lambda : [])
M = int(500000.0 + 5)

def pre():
	for i in range(1, M + 1):
		for j in range(i, M + 1, i):
			divs[j].append(i)
	return divs

def main():
	pre()
	for _ in range(int(input())):
		(N, m) = [int(x) for x in input().split()]
		count = 0
		for b in range(2, N + 1):
			x = m - m % b
			if x != 0:
				count += divs[x].index(b)
			else:
				count += b - 1
		print(count)
main()


def lower_bound(arr, val):
	n = len(arr)
	low = 0
	high = n
	while low < high:
		mid = (high + low) // 2
		if arr[mid] >= val:
			high = mid
		else:
			low = mid + 1
	if arr[low] < val:
		low = low + 1
	return low
maxm = int(500000.0 + 1)
div = [[] for i in range(maxm)]
for i in range(1, maxm):
	for j in range(i, maxm, i):
		div[j].append(i)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	for b in range(2, n + 1):
		x = m - m % b
		if x > 0:
			ans += lower_bound(div[x], b)
		else:
			ans += b - 1
	print(ans)


def preCalcMod():
	factors = []
	M = 500000
	factors.insert(0, [])
	for i in range(1, M + 1):
		j = i
		while j <= M:
			if i == 1:
				factors.insert(j, [])
			factors[j].append(i)
			j += i
	return factors

def modularEquation():
	factors = preCalcMod()
	T = int(input())
	for i in range(0, T):
		(N, M) = map(int, input().split())
		count = 0
		for b in range(2, min(N, M) + 1):
			T = M - M % b
			if T == 0:
				break
			for key in factors[T]:
				if key < b:
					count += 1
				else:
					break
		if N > M:
			a = M
			lastTerm = N - 1
			nBy2 = (N - M) / 2
			sumIs = nBy2 * (a + lastTerm)
			count += int(sumIs)
		print(count)
modularEquation()


import math
from collections import Counter, defaultdict
import sys
input = sys.stdin.readline
readInt = lambda : int(input().strip())
readfloat = lambda : float(input().strip())
readStr = lambda : input().strip()
intList = lambda : list(map(int, input().strip().split()))
intMap = lambda : map(int, input().strip().split())
floatList = lambda : list(map(float, input().strip().split()))
floatMap = lambda : map(float, input().strip().split())
strList = lambda : list(input().strip().split())

def solve(n, m):
	res = 0
	if n > m:
		tn = n - m
		res += tn * (tn + 1) // 2
	else:
		tn = 0
	res += (m - 1) * tn
	p = min(n, m)
	c = Counter()
	res += p - 1
	for a in range(2, p + 1):
		mod = m % a
		res += c[mod]
		for b in range(mod, p + 1, a):
			c[b] += 1
	return res
for _ in range(readInt()):
	(n, m) = intMap()
	print(solve(n, m))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [1] * (n + 1)
	count = 0
	for i in range(2, n + 1):
		a = m % i
		count += l[a]
		for j in range(a, n + 1, i):
			l[j] += 1
	print(count)


M = 500000.0 + 5
factor = {}
for i in range(1, int(M)):
	for j in range(i, int(M), i):
		factor.setdefault(j, []).append(i)
t = int(input())
for _ in range(t):
	(N, M) = map(int, input().split())
	ans = 0
	for i in range(2, N + 1):
		X = M - M % i
		if X != 0:
			ans += factor[X].index(i)
		else:
			ans += i - 1
	print(ans)


from bisect import bisect_left
M = 5 * 10 ** 5

def precompute_divisors(m):
	arr = []
	for i in range(m + 1):
		arr.append([])
	for i in range(1, m + 1):
		for j in range(i, m + 1, i):
			arr[j].append(i)
	return arr

def solve_modular(n, m, arr):
	result = 0
	for b in range(n, 1, -1):
		x = b * (m // b)
		if x != 0:
			result += bisect_left(arr[x], b)
		else:
			result += b - 1
	return result
pre = precompute_divisors(M)
for t in range(int(input())):
	(n, m) = map(int, input().split())
	ans = solve_modular(n, m, pre)
	print(ans)


for i in range(int(input())):
	(N, M) = map(int, input().split())
	count = 0
	arr = [1 for i in range(N + 1)]
	for a in range(2, N + 1):
		count += arr[M % a]
		for b in range(M % a, N + 1, a):
			arr[b] += 1
	print(count)


lim = 5 * 10 ** 5 + 1
factors = [-1] * lim
for i in range(1, lim):
	j = 1
	while i * j < lim:
		try:
			factors[i * j].append(i)
		except:
			factors[i * j] = [i]
		j += 1
from bisect import bisect_left as lower_bound
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	count = 0
	for b in range(2, n + 1):
		x = m - m % b
		a = factors[x]
		if x <= 0:
			count += b - 1
		else:
			count += lower_bound(a, b)
	print(count)


from bisect import bisect_left as lower_bound
factors = []
m = 5 * 10 ** 5 + 1

def compute_factors(m):
	for i in range(m):
		factors.append([1])
	for i in range(2, m):
		for j in range(i, m, i):
			factors[j].append(i)
T = int(input())
compute_factors(m)
for _ in range(T):
	(N, M) = map(int, input().split())
	res = 0
	for b in range(2, N + 1):
		x = M - M % b
		if x > 0:
			res += lower_bound(factors[x], b)
		else:
			res += b - 1
	print(res)


mx = 500015
a = [list() for x in range(mx)]

def PreCompute():
	for i in range(1, mx):
		for j in range(i, mx, i):
			a[j].append(i)

def Lower_bound(fr, value):
	(l, r) = [0, len(a[fr]) - 1]
	ans = 0
	while l <= r:
		mid = l + r >> 1
		if a[fr][mid] < value:
			ans = mid
			l = mid + 1
		else:
			r = mid - 1
	return ans + 1
PreCompute()
t = int(input())
while t:
	t -= 1
	cnt = 0
	(n, m) = [int(x) for x in input().split()]
	for b in range(2, n + 1):
		x = m - m % b
		if x > 0:
			cnt += Lower_bound(x, b)
		else:
			cnt += b - 1
	print(cnt)


def modEquation(n, m, fact):
	ans = 0
	for b in range(2, n + 1):
		t = m - m % b
		if b > m:
			ans += b - 1
		else:
			f = fact[t]
			st = 0
			en = len(f) - 1
			while st <= en:
				mid = (st + en) // 2
				if f[mid] < b:
					st = mid + 1
				else:
					en = mid - 1
			ans += st
	return ans

def main():
	fact_s = int(500000.0) + 1
	fact = [[] * fact_s for i in range(fact_s)]
	for i in range(1, fact_s):
		for j in range(i, fact_s, i):
			fact[j].append(i)
	for i in range(int(input().strip())):
		(n, m) = map(int, input().strip().split(' '))
		print('{0}'.format(modEquation(n, m, fact)))
main()


def solve(n, m):
	v = 0
	arr = [1 for i in range(n + 1)]
	for i in range(2, n + 1):
		a = m % i
		v += arr[a]
		for j in range(a, n + 1, i):
			arr[j] += 1
	return v
t = int(input())
while t != 0:
	(n, m) = map(int, input().split())
	print(solve(n, m))
	t -= 1


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	count_by_mod = [1] * (N + 1)
	res = 0
	for b in range(2, N + 1):
		mod_b = M % b
		res += count_by_mod[mod_b]
		for mod in range(mod_b, N + 1, b):
			count_by_mod[mod] += 1
	print(res)


import bisect
M = int(500000.0) + 5
dividors = [[] for _ in range(M)]
for i in range(1, M):
	for j in range(i, M, i):
		dividors[j].append(i)
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	ans = 0
	if n > m:
		ans += (m + n - 1) * (n - m) // 2
	for b in range(1, min(n, m) + 1):
		x = m - m % b
		ans += bisect.bisect_left(dividors[x], b)
	print(ans)


t = int(input())
for test in range(t):
	(n, m) = map(int, input().split())
	c = 0
	f = 0
	if n > m:
		x = n - m
		c += x * m
		c += x * (x - 1) // 2
		n = m
	c += n - 1
	d = {}
	for i in range(n, 1, -1):
		x = m % i
		f = max(f, x)
		try:
			d[x] += 1
			c += d[x] - 1
			p = 1
			q = 0
			z = 0
			while z < f:
				z = x + p * i
				try:
					q += d[z]
					p += 1
				except:
					p += 1
			c += q
		except:
			d[x] = 1
			p = 1
			q = 0
			z = 0
			while z < f:
				z = x + p * i
				try:
					q += d[z]
					p += 1
				except:
					p += 1
			c += q
	print(c)


try:
	import sys
	from sys import stdin
	for _ in range(int(input())):
		(n, m) = map(int, sys.stdin.readline().split())
		l = [1] * (n + 1)
		count = 0
		for i in range(2, n + 1):
			y = m % i
			count += l[y]
			for j in range(y, n + 1, i):
				l[j] += 1
		print(count)
except Exception:
	pass


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = [1] * (n + 1)
	c = 0
	for j in range(2, n + 1):
		x = m % j
		c += a[x]
		for p in range(x, n + 1, j):
			a[p] += 1
	print(c)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	val = 0
	ar = [1 for i in range(n + 1)]
	for j in range(2, n + 1):
		rem = m % j
		val += ar[rem]
		for k in range(rem, n + 1, j):
			ar[k] += 1
	print(val)


try:

	def solution(n, m):
		va = 0
		arr = [1 for i in range(n + 1)]
		for i in range(2, n + 1):
			a = m % i
			va += arr[a]
			for j in range(a, n + 1, i):
				arr[j] += 1
		return va
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		print(solution(n, m))
except:
	pass


t = int(input())
while t:
	t -= 1
	(n, m) = list(map(int, input().split()))
	count = 0
	l = [1] * (n + 1)
	for i in range(2, n + 1):
		a = m % i
		count += l[a]
		for j in range(a, n + 1, i):
			l[j] += 1
	print(count)


t = int(input())
while t > 0:
	nm = list(map(int, input().strip().split()))
	(n, m) = (nm[0], nm[1])
	ans = 0
	li = [1] * (n + 1)
	for i in range(2, n + 1):
		a = m % i
		ans += li[a]
		for j in range(a, n + 1, i):
			li[j] += 1
	print(ans)
	t -= 1


t = int(input())
for iii in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n + 1):
		l.append(int(1))
	ans = 0
	for a in range(2, n + 1):
		x = m % a
		ans += l[x]
		for b in range(x, n + 1, a):
			l[b] += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	cop = 0
	me = [1] * (n + 1)
	for a in range(2, n + 1):
		x = m % a
		cop += me[x]
		for b in range(x, n + 1, a):
			me[b] += 1
	print(cop)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	main = [1 for i in range(n + 1)]
	for i in range(2, n + 1):
		a = m % i
		ans += main[a]
		for j in range(a, n + 1, i):
			main[j] += 1
	print(ans)


try:
	t = int(input())
	while t:
		(n, m) = map(int, input().split())
		res = 0
		modArr = [1] * (n + 1)
		for i in range(2, n + 1):
			a = m % i
			res += modArr[a]
			for j in range(a, n + 1, i):
				modArr[j] += 1
		print(res)
		t -= 1
except:
	pass


from functools import reduce

def main():
	T = int(input())
	for i in range(T):
		val = input().split()
		N = int(val[0])
		M = int(val[1])
		total = 0
		arr = [1] * (N + 1)
		j = 2
		while j <= N:
			modVal = M % j
			total = total + arr[modVal]
			k = modVal
			while k <= N:
				arr[k] = arr[k] + 1
				k = k + j
			j = j + 1
		print(total)
main()


def solve():
	t = int(input())
	for i in range(t):
		(N, M) = map(int, input().split())
		a = [1] * (N + 1)
		cnt = 0
		for j in range(2, N + 1):
			c = M % j
			cnt += a[c]
			for k in range(c, N + 1, j):
				a[k] = a[k] + 1
		print(cnt)

def main():
	solve()
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [1] * (n + 1)
	k = 0
	for i in range(2, n + 1):
		md = m % i
		k += arr[md]
		p = md
		while p <= n:
			arr[p] += 1
			p += i
	print(k)


t = int(input())
for i in range(t):
	arr = [int(x) for x in input().split()]
	(n, m) = (arr[0], arr[1])
	l = [1] * (n + 1)
	an = 0
	for io in range(2, n + 1):
		a = m % io
		an += l[a]
		for j in range(a, n + 1, io):
			l[j] += 1
	print(an)


from sys import stdin

def fact(z, b):
	c = 0
	l = []
	for i in range(1, int(z ** 0.5) + 1):
		if z % i == 0:
			if i != z // i:
				l.append(i)
				l.append(z // i)
			else:
				l.append(i)
	for i in l:
		if i < b:
			c += 1
	return c
t = int(stdin.readline())
for e in range(t):
	(n, m) = stdin.readline().split()
	n = int(n)
	m = int(m)
	co = 0
	l = [1] * (n + 1)
	for i in range(2, n + 1):
		a = m % i
		co += l[a]
		for j in range(a, n + 1, i):
			l[j] += 1
	print(co)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	res = 0
	arr = [1 for i in range(n + 1)]
	for i in range(2, n + 1):
		a = m % i
		res += arr[a]
		for j in range(a, n + 1, i):
			arr[j] += 1
	print(res)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	l = [1] * (n + 1)
	for a in range(2, n + 1):
		x = m % a
		c += l[x]
		for b in range(x, n + 1, a):
			l[b] += 1
	print(c)


t = int(input())
for i in range(t):
	(N, M) = [int(x) for x in input().split()]
	result = 0
	list_array = [1 for j in range(N + 1)]
	for a in range(2, N + 1):
		x = M % a
		result += list_array[x]
		for b in range(x, N + 1, a):
			list_array[b] += 1
	print(result)


for i in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, m) = (x[0], x[1])
	l = [1] * (n + 1)
	ans = 0
	for i in range(2, n + 1):
		a = m % i
		ans += l[a]
		for j in range(a, n + 1, i):
			l[j] += 1
	print(ans)