Lcm

时间限制:40s      空间限制:512MB

题目描述

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


输入格式

第一行一个整数T表示数据组数。接下来T行每行两个整数A,B表示一组数据。
T ≤ 2000,A,B ≤ 4 × 10^6


输出格式

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


样例输入

5
2 2
4 6
3 4
5 1
23333 33333

样例输出

7
148
48
15
451085813

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose