题目描述

给定 $A,B$，求

求所有满足如下条件的有序数对 $(a,b)$ 的 ${\rm lcm}(a,b)$ 之和。

1. $1\le a\le A$，$1\le b\le B$。
2. 不存在 $m>1$，使得 $m|\gcd(a,b)$。

答案对 $2^{30}$ 取模。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，每行两个整数 $A,B$，表示一组数据。

输出格式

对每组数据输出一行一个整数表示答案模 $2^{30}$ 的值

5
2 2
4 6
3 4
5 1
23333 33333

7
148
48
15
451085813

提示

$1\le T\le 2000$，$1\le A,B\le 4\times 10^6$。

题目来源

没有写明来源