B2. Reverse Card (Hard Version) 卡牌反转（困难版）

时间限制：每个测试用例 $2$ 秒
内存限制：$256$ 兆字节

两版题目是不同的问题，建议把两个版本都阅读一遍。 只有同时通过简单版和困难版，才可以进行 hack 操作。

题目描述

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

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

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

输入格式

本题有多组测试用例。 第一行一个整数 $t$（$1 \le t \le 10^4$），代表测试用例组数。

每组测试用例输入一行两个整数 $n,m$（$1 \le n,m \le 2\times 10^6$）。

题目保证： 所有测试用例的 $n$ 之和不超过 $2\times 10^6$， 所有测试用例的 $m$ 之和也不超过 $2\times 10^6$。

输出格式

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

样例输入

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

样例输出

0
1
1
6
423
5933961

样例说明

第一组测试用例：没有任何数对满足条件，答案为 $0$。

第四组测试用例中，合法数对为： $(2,2),(3,6),(4,4),(6,3),(6,6),(8,8)$，共 $6$ 个。