题目描述

徐老师有一个 $n$ 个点（点的编号为 $1 \sim n$ ）的完全图

对于任意两点 $i,j$ ，这两点之间的边长为 $lcm(i + 1,j + 1)$

徐老师最近刚学习了 $Kruskal$ 算法，他自己计算出了这个最小生成树，但是他希望你帮他验证一下他的结果是否正确

所以请你计算一下这个图的最小生成树的边权值总和是多少

当然因为数据过大，所以将结果对 $MOD$ 取模

注：

1. 完全图：即任意两个点之间都存在一条边
2. $lcm$ 表示最小公倍数
3. 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部 $n$ 个顶点，但只有足以构成一棵树的 $n-1$ 条边。
4. 一颗有 $n$ 个顶点的生成树有且仅有 $n-1$ 条边，如果生成树中再添加一条边，则必定成环。
5. 最小生成树：在一个图的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

输入格式

输入第一行包含一个整数 $T$ 表示共有 $T$ 组测试数据 接下来 $T$ 行，每行包含两个整数 $n,MOD$ 含义如题

输出格式

对于每组测试数据，输出一行包含一个整数，表示对 $MOD$ 取模以后的答案

数据范围

对于 $40\%$ 的数据，$1 \leq T \leq 5,n \leq 10^4$ 对于 $100\%$ 的数据，$1 \leq T \leq 50,n \leq 10^7, 10^8 \leq MOD \leq 10^{10}$，且保证 $MOD$ 是质数

样例输入

2
3 99999773
100 99999773

样例输出

10
6307