#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <iomanip>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define dbg(a) cout<<a<<endl
#define clr(a) memset(a,0,sizeof(a))
#define maxn 10001
#define mod 1000000007
#define eps 1e-9
#define inf 0x7fffffff
ll mlt (ll a,ll b,ll p)
{
    a%=p;
    b%=p;
    ll res = 0;
    while (b)
    {
        if (b&1)
        {
            res+=a;
            if (res>=p) res-=p;
        }
        b>>=1;
        a<<=1;
        if (a>=p) a-=p;
    }
    return res;
}
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        ll p,q;
        scanf("%I64d%I64d",&q,&p);
        ll a,b;
        if (q%2==0)
        {
            a=(q-2)/2;
            b=q-1;
        }
        else
        {
            a=q-2;
            b=(q-1)/2;
        }
        ll res = mlt(a,b,p);
        printf("%I64d\n",res);

    }
    return 0;
}