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

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

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

• $1 \le a \le n$，$1 \le b \le m$；
• $b \cdot \gcd(a, b)$ 是 $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

0
1
1
6
423
5933961

说明

在第一个测试用例中，没有数对满足条件。

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