---

暴力很容易写，找一下规律，可以发现：

实际上不用找规律，显然\(2 \to p\)，每个合数肯定是被某个质因子连上去

对于质数\(p(>3)\)，首先有\(2 \to p\)的边，之后有\(p \to p \cdot (p+2k)\)的边，其中\(k=0,1,2,3,\cdots\)

最后连上\(2 \to *\)，其中\(*\) 从未被连过

那就很容易发现，\(*\)只能是偶数或者素数

现在需要求mst

如果\(p+k=a \cdot b,a<p\)，那么\(p(p+k)=a \cdot pb=a \cdot (a+2k)\)

所以每个奇数\(t\)只会在其最小质因子处统计，这些边的贡献是\(t\)

\(2 \to p\)的贡献是\(2p\)

\[\left( \sum_{2<p\le n+1,p \in \mathbb{P}} 2p \right)+\sum_{2 \le t \le n+1, t \not\in \mathbb{P}} t=\left( \sum_{i=3}^{n+1}i \right)+\sum_{2 < p \le n+1 ,p \in \mathbb{P}} p \]

懒得写min25筛了，网上贺了个板子

#include <bits/stdc++.h>
using namespace std;

int calc(int n) {
    vector<int> fa(n + 1);
    function<int(int)> getfa = [&] (int x) {
        return x == fa[x] ? x : fa[x] = getfa(fa[x]);
    };
    for(int i = 1 ; i <= n ; ++ i) {
        fa[i] = i;
    }
    int res = 0;
    function<int(int, int)> gcd = [&] (int a, int b) {
        return b ? gcd(b, a % b) : a;
    };
    auto lcm = [&] (int a, int b) {
        return a / gcd(a, b) * b;
    };
    vector<pair<int, pair<int, int> > > ed;
    for(int i = 1 ; i <= n ; ++ i) {
        for(int j = i + 1 ; j <= n ; ++ j) {
            ed.push_back({ lcm(i + 1, j + 1), { i, j } });
        }
    }
    vector<pair<pair<int, int>, int> > out;
    sort(ed.begin(), ed.end());
    for(auto e: ed) {
        int w = e.first;
        int u = e.second.first, v = e.second.second;
        if(getfa(u) != getfa(v)) {
//            printf("%d - %d (%d)\n", v + 1, u + 1, w);
//            printf("%d %d %d\n", v + 1, u + 1, w);
            out.push_back({ {u + 1, v + 1}, w }); 
            fa[getfa(u)] = getfa(v);
            res += w;
        }
    }
//    sort(out.begin(), out.end());
//    for(auto x: out) {
//        printf("%d %d %d\n", x.first.first, x.first.second, x.second);
//    }
    return res;
}

int calc_test(int n) {
    vector<int> vis(n + 5), fa(n + 5), linked(n + 5);
    function<int(int)> getfa = [&] (int x) {
        return x == fa[x] ? x : fa[x] = getfa(fa[x]);
    };
    for(int i = 2 ; i <= n + 1 ; ++ i) {
        fa[i] = i;
    }
    function<int(int, int)> gcd = [&] (int a, int b) {
        return b ? gcd(b, a % b) : a;
    };
    auto lcm = [&] (int a, int b) {
        return a / gcd(a, b) * b;
    };
    int res = 0;
    for(int i = 2 ; i <= n + 1 ; i += 2) vis[i] = 1;
    for(int i = 3 ; i <= n + 1 ; ++ i) {
        if(!vis[i]) {
            linked[i] = 1;
            res += lcm(2, i); 
            for(int j = i ; j <= n + 1 ; j += i) vis[j] = 1;
            for(int j = i ; i * j <= n + 1 && j <= n + 1 ; j += 2) {
                int t = i * j;
                if(!linked[t]) {
                    linked[t] = 1;
//                    cout << i << ' ' << t << endl;
                    res += lcm(i, t);
                }
            }
        }
    }
    for(int i = 3 ; i <= n + 1 ; ++ i) {
        if(!linked[i]) {
//            cout << 2 << ' ' << i << endl;
            res += lcm(2, i);
        }
    }
    return res;
}

int calc_test_test(int n) {
    vector<int> vis(n + 5);
    int res = 0;
    for(int i = 2 ; i <= n + 1 ; ++ i) {
        if(i > 2) {
            res += i;
        }
        if(!vis[i]) {
            if(i != 2) {
                res += i;
            }
            for(int j = i ; j <= n + 1 ; j += i) {
                vis[j] = 1;
            }
        }
    }
    return res;
}
typedef long long ll;
ll mod;
namespace getP {
    // http://www.shallowdreams.cn/?p=266
    // 不想写了，粘的板子 
   const int N = 1000010;
    int prime[N], id1[N], id2[N], flag[N], ncnt, m;
    ll g[N], sum[N], a[N], T;
    ll n;
    int ID(ll x) {
        return x <= T ? id1[x] : id2[n / x];
    }
    ll calc(ll x) {
        return x * (x + 1) / 2 - 1;
    }
    ll f(ll x) {
        return x;
    }
    ll init(ll n){
        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]);
    }
    ll solve(ll x){
        if(x<=1){return x;}
        memset(g,0,sizeof(g));
        	memset(a,0,sizeof(a));
        	memset(sum,0,sizeof(sum));
        	memset(prime,0,sizeof(prime));
    	memset(id1,0,sizeof(id1));
    	memset(id2,0,sizeof(id2));
    	memset(flag,0,sizeof(flag));
    	ncnt=m=0;
        return n=x,init(n),g[ID(n)];
    }
}

typedef long long ll;
ll nekkonya(ll n) {
    // 2 ~ n + 1
    if(n == 1) return 0;
    else if(n == 2) return 6;
    else if(n == 3) return 10;
    else if(n == 4) return 20;
    else if(n == 5) return 26;
    
    ll res = getP :: solve(n + 1) - 2;
    res %= mod;
    res += (ll) (3 + n + 1) % mod * ((n - 1) % mod) % mod * ((mod + 1) / 2) % mod;
    res %= mod;
    res = (res + mod) % mod;
    return res;
}

int main() {
    int t; cin >> t;
    while(t --) {
        ll n;
        cin >> n >> mod;
        cout << nekkonya(n) << endl;
    }
}