#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <cmath>
#include <set>

using namespace std;

#define rep(i, l, r) for(int i=l; i<=r; i++)
#define    dow(i, l, r) for(int i=l; i>=r; i--)
#define travel(x) for(edge *p=fir[x]; p; p=p->n)
#define travel_sap(x) for(edge *p=fir[x]; p; p=p->n)
#define clr(x,c) memset(x, c, sizeof(x))

typedef pair<int,int> Pii;
typedef long long ll;

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define lowbit(x) (x&-x)
#define l(x) Left[x]
#define r(x) Right[x]

#define maxn 100009

inline int read()
{
    int x=0, f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while ('0'<=ch && ch<='9') x=x*10+ch-'0', ch=getchar();
    return x*f;
}

ll p, Q;

int main()
{
    int t=read(); while (t--)
    {
        scanf("%lld%lld", &p, &Q);
        ll A=0, a=p-2, b=p-1; if (b%2==0) b/=2; else a/=2;
        while (b)
        {
            if (b&1) (A+=a)%=Q;
            b>>=1, (a+=a)%=Q;
        }
        printf("%lld\n", A%Q);
    }
    return 0;
}