#define filer() freopen("in.txt","r",stdin)
#define filew() freopen("out.txt","w",stdout)
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include <map>
#define INF 1<<29
#define PI pair<int,int>
#define f first
#define s second
#define SET(a, x) memset((a), (x), sizeof(a))
#define pb push_back
#define i64 long long
#define EPS (1e-9)
using namespace std;
typedef vector<int> VI;
typedef vector<PI> vii;
//i64 INF=(i64)((i64)1<<(i64)59);

i64 N,p;

i64 BigMod(i64 a,i64 p,i64 m)
{
    if(!p)return 1;
    if(p%2)return ((a%m)*BigMod(a,p-1,m)%m)%m;
    i64 ta=BigMod(a,p/2,m);
    return ((ta%m)*(ta%m))%m;
}



int main()
{
    //filer();
    int T,cas=0;
    int i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&N,&p);

        i64 m=N/p;
        i64 ans=BigMod(p-1,m,p);
        m=N%p;
        for(i=1;i<=m;i++)
        {
            ans*=i;
            ans%=p;
        }
        printf("%lld\n",ans);
        /*ans=1;
        for(i=1;i<=N;i++)
        {
            if(i%p==0)continue;
            ans*=(i%p);
            ans%=p;
        }
        cout<<ans<<endl;*/
    }
    return 0;
}
/*
Test Case:

*/