#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + ;

int n;

ll ans = , P;

ll f[N], g[N];

int m[N];

int rd()

{

    int x = , f = ;

    char c = getchar();

    while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

    while(c >= '' && c <= '') { x = x *  + c - ''; c = getchar(); }

    return x * f;

}

ll power(ll x, ll t)

{

    ll ret = ;

    for(; t; t >>= , x = x * x % P) if(t & ) ret = ret * x % P;

    return ret;

}

ll inv(ll x)

{

    return power(x, P - );

}

int main()

{

    int T = rd();

    while(T--)

    {

        n = rd();

        P = rd();

        f[] = ;

        f[] = ;

        for(int i = ; i <= n; ++i) f[i] = (f[i - ] *  + f[i - ]) % P;

        for(int i = ; i <= n; ++i) g[i] = f[i];

        for(int i = ; i <= n; ++i)

        {

            ll t = inv(g[i]);

            for(int j = i + i; j <= n    ; j += i)

                g[j] = g[j] * t % P;

        }

        ll lcm = ;

        ans = ;

        for(int i = ; i <= n; ++i)

        {

            lcm = lcm * g[i] % P;

            ans = (ans + 1LL * lcm * i) % P;

        }

        printf("%lld\n", ans);

    }

    return ;

}