内存限制：512 MiB
时间限制：5000 ms
标准输入输出
题目类型：传统
评测方式：文本比较
到底是互质还是整除？
有 组询问，每次给定 ，求：
由于答案会很大，你只需要输出答案对 取模的结果。
上式中：
- 是欧拉函数， 表示 中与 互质的数的个数。
- 是约数和函数， 表示 的所有约数之和。
第一行一个正整数 ，表示有 组询问。
接下来 行，每行两个正整数 ，表示一次询问。
输入输出样例 #1
输入 #1
8
2 2
3 3
4 4
5 5
6 6
7 7
114 514
2333 23333
输出 #1
14
130
566
2310
4778
13934
603971168
547492264
说明/提示
对于 的数据：保证
对于 的数据：保证 。
来源：洛谷