两个版本是不同的问题。您可能想阅读这两个版本。只有两个版本都解决了,你才能进行黑客攻击。
给你两个正整数 $$$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)$$$满足条件。