# 2020 CCPC网络赛 Graph Theory Class(min

1 − n 1-n 的最小生成树，边权为 l c m ( i + 1 , j + 1 ) lcm(i+1,j+1) i , j i,j 属于 1 − n 1-n

/*
* @Author: vain
* @Date: 2020
* @LastEditTime: 2020-09-22 11:55:05
* @LastEditors: sueRimn
* @Description: 学不会 dp 的 fw
* @FilePath: \main\demo.cpp
*/
//#include bits/stdc++.h
#include cstdio
#include algorithm
#include iostream
#include vector
#include map
#include queue
#include set
#include ctime
#include cstring
#include cstdlib
#include math.h
#include bitset
using namespace std;
typedef long long ll;
#define ll long long
//typedef unsigned long long uint;
const int N = 1e3 + 20;
const int maxn = 1e7 + 20;
// typedef pairint, int p;
// priority_queuep, vectorp, greaterp m;
//int sum[maxn];
ll mod;
int max(int a, int b) { return a  b ? a : b; }
int min(int a, int b) { return a  b ? a : b; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
void swap(int x, int y) { x ^= y, y ^= x, x ^= y; }
//int ik[N], q[N], cnt;
int lowbit(int x) { return (x)  (-x); }
//vectorint f;
int h[maxn], p[maxn];
const int base = 13331;
char s[maxn];
ll ksm(ll a, ll b)
{
ll res = 1;
a %= mod;
while (b)
{
if (b % 2 == 1)
res = (a * res) % mod;
b = 1ll;
a = (a % mod) * (a % mod) % mod;
}
return res;
}
int ksc(int x, int y, int mod)
{
return (x * y - (int)((long double)x / mod * y) * mod + mod) % mod;
}

ll prime[maxn], id1[maxn], id2[maxn], flag[maxn], ncnt, m;

ll g[maxn], sum[maxn], a[maxn], T, n;

inline int ID(ll x)
{
return x = T ? id1[x] : id2[n / x];
}

inline ll calc(ll x)
{
return x * (x + 1) / 2 - 1;
}

inline ll f(ll x)
{
return x;
}

inline void init()
{
T = sqrt(n + 0.5);
for (int i = 2; i = T; i++)
{
if (!flag[i])
prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
for (int j = 1; j = ncnt  i * prime[j] = T; j++)
{
flag[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
for (ll l = 1; l = n; l = n / (n / l) + 1)
{
a[++m] = n / l;
if (a[m] = T)
id1[a[m]] = m;
else
id2[n / a[m]] = m;
g[m] = calc(a[m]);
}
for (int i = 1; i = ncnt; i++)
for (int j = 1; j = m  (ll)prime[i] * prime[i] = a[j]; j++)
g[j] = g[j] - (ll)prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]);
}

inline ll solve(ll x)
{
if (x = 1)
return x;
return n = x, init(), g[ID(n)];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// srand(time(unsigned int));
int t;
cin  t;
//Sum(10000);
while (t--)
{
ncnt = m = 0;
cin  n  mod;

ll s = ((3ll + (n % mod)) * (n % mod) % mod) * ksm(2, mod - 2) % mod;
//cout  sum  endl;
ll x = solve(n + 1ll) % mod;
//cout  x  endl;
ll ans = (s - x + mod) % mod;
x = (x - 2 + mod) % mod;
ll res = ((x * 2ll % mod) + ans) % mod;
cout  res  endl;
}
}