这两个版本是不同的问题。你可能需要阅读两个版本。只有当两个版本都被解决时，你才能进行 hack。

给你两个正整数 $n, m$。

计算满足以下条件的有序对 $(a, b)$ 的数量：

• $1 \le a \le n, 1 \le b \le m$；
• $a + b$ 是 $b \cdot \gcd(a, b)$ 的倍数。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$ ($1 \le n, m \le 2 \cdot 10^6$)。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2 \cdot 10^6$。

输出格式

对于每个测试用例，输出一个整数：满足条件的有序对数量。

样例

输入样例 1

6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141

输出样例 1

1
3
4
14
153
1643498

说明

在第一个测试用例中，只有 $(1, 1)$ 满足条件。

在第四个测试用例中，$(1, 1), (2, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 1), (6, 2), (6, 3), (7, 1), (8, 1), (9, 1), (10, 1), (10, 2)$ 满足条件。