『湖南省队集训』lcm

给出$A,B$，考虑所有满足$1\le a\le A$，$1\le b\le B$，且不存在$n>1$使得$n^2$同时整除$a$和$b$的有序数对$(a,b)$，求其${\mathrm{lcm}}(a,b)$之和。答案模$2^{30}$。

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

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

5
2 2
4 6
3 4
5 1
23333 33333

对于$20\%$数据，$T\le 10$，$A,B\le 500$。

对于$30\%$数据，$T\le 10$，$A,B\le 2000$。

对于$40\%$数据，$T\le 10$，$A,B\le 2\times 10^5$。

对于$60\%$数据，$T\le 10$，$A,B\le 4\times 10^6$。

对于所有数据，$T\le 2000$，$A,B\le 4\times 10^6$。