Time Limit: 1 Sec
Memory Limit: 256 MB
Submission：1
AC：1
Score：10
蒜头君有一个 n 个点（点的编号为 1 ~ n 的完全图
对于任意两点 i,j ，这两点之间的边长为 lcm(i + 1,j + 1)
蒜头君最近刚学习了 Kruskal 算法，他自己计算出了这个最小生成树，但是他希望你帮他验证一下他的结果是否正确
所以请你计算一下这个图的最小生成树的边权值总和是多少
当然因为数据过大，所以将结果对 MOD 取模
注：
1. 完全图：即任意两个点之间都存在一条边
2. lcm 表示最小公倍数
3. 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部 n 个顶点，但只有足以构成一棵树的 n-1 条边。
一颗有 n 个顶点的生成树有且仅有 n-1 条边，如果生成树中再添加一条边，则必定成环。
4. 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
输入第一行包含一个整数 T 表示共有 T 组测试数据
接下来 T 行，每行包含两个整数 n,MOD 含义如题
对于每组测试数据，输出一行包含一个整数，表示对 MOD 取模以后的答案
input:
2
3 99999773
100 99999773
output:
10
6307
对于 $40\%$ 的数据，$1 <= T
<= 5,n
<= 10^4$
对于 $100\%$ 的数据，$1 <= T
<= 50,n
<= 10^7, 10^8
<= MOD
<= 10^10$，且保证 $MOD$ 是质数