题目背景

275307894a 在 NOI2024D2T1 这个数论题上暴毙了，于是 275307894a 要加训数论。

题目描述

给定两个整数 $n,m$，你需要对满足以下条件的二元组 $(a,b)$ 计数：

• $1\leq a\leq n,1\leq b\leq m$。
• $(a+b)\mid (b\times \gcd(a,b))$

输入格式

本题单个测试点内有多组测试数据，第一行一个整数 $T$ 表示数据组数。

对于每组数据，一行两个整数 $n,m$。

输出格式

对于每组数据，输出答案。

样例

样例输入 1

3
5 3
3 4
2 3

样例输出 1

1
1
1

样例输入 2

3
11962 9544
1322 5153
16716 15303

样例输出 2

38318
6657
60541

提示与说明

记 $N=\sum n,M=\sum m$

对于所有数据，$T\leq 3,n,m\geq 1,1\leq N,M\leq 3\times 10^6$。