说明

本题保证数据随机生成

有一个 $n$ 个点的完全图，结点编号为 $1,2……n$，结点 $i,j$ 之间有权值为 $\mathrm{lcm}(i,j)+\mathrm{gcd}(i,j)$ 的无向边。

请你求出这个图的最大生成树的大小，对 $2^{32}$ 取模。

输入格式

本题有多组测试数据，第一行一个整数 $T$ 代表数据组数。

接下来 $T$ 行，每行一个整数 $n$ 代表点数。

输出格式

共 $T$ 行，每行一个整数代表一组数据的答案。

9
10
1000
100000
10000000
1000000000
100000000000
10000000000000
1000000000000000
100000000000000000

422
499008694
4172096327
3128649679
2692599804
194024000
2969759816
505684415
3052141644

提示

有子任务限制

• 对于 $5\%$ 的数据，$T=1,n\leq 2000$。
• 对于 $15\%$ 的数据，$T=1,n\leq 10^6$。
• 对于 $30\%$ 的数据，$T=1,n\leq 10^8$。
• 对于 $50\%$ 的数据，$T=1,n\leq 10^{10}$。
• 对于 $75\%$ 的数据，$T=1,n\leq 10^{15}$。
• 对于 $100\%$ 的数据，$T\leq 10,n\leq 10^{18}$。

下发文件中提供了一份高速的 Pollard_Rho 分解质因数代码。