#P4659. Lcm

Lcm

题目描述

给定 A,BA,B,求

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

  1. 1≤a≤A1\le a\le A,1≤b≤B1\le b\le B。
  2. 不存在 m>1m>1,使得 m∣gcd⁡(a,b)m|\gcd(a,b)。

答案对 2302^{30} 取模。

输入格式

第一行一个整数 TT 表示数据组数。

接下来 TT 行,每行两个整数 A,BA,B,表示一组数据。

输出格式

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

5
2 2
4 6
3 4
5 1
23333 33333
7
148
48
15
451085813

提示

1≤T≤20001\le T\le 2000,1≤A,B≤4×1061\le A,B\le 4\times 10^6。

题目来源

没有写明来源