#include"iostream"
using namespace std;
#include"map"
#include"math.h"
#include <algorithm>
#define N 100
#define M 2*N
int a[N];__int64 c[N][N] = {0};
int rep[M];//各置換循環(huán)節(jié)數(shù)
void rotate(int n)//旋轉(zhuǎn)的循環(huán)節(jié)總數(shù)
{	int b[N];int i,j;
	for( i = 0;i < n; i++)	a[i] = i;
	for(	i = 1;i <= n-1; i++)
	{	int t = a[0];
		for( j = 0;j < n-1; j++) a[j] = a[j+1];
		a[n-1] = t;		//設(shè)置置換類
		memset(b,0,sizeof b);
		int knob = 0;
		for( j = 0;j < n; j++){
			if(b[j]) continue;
			for(int k = a[j]; k != j; k = a[k]) {b[k] = 1;}
			knob++;
		}
		rep[i] = knob;
	}
}
__int64 polya(int n,int m)
{
	if(n == 0) return 0;
	__int64 p = 0;
	for(int i = 0;i < n; i++) {
		p += (__int64)pow((double)m,rep[i]);
	}
	return p/n;
}
__int64 com(int m,int j)
{
	if(c[m][j]) return c[m][j];
	if(j == 0) return 1;
	else return c[m][j] = com(m-1,j-1)*m/j;
}
int main()
{	int n,m,j,k;__int64 sum = 0;
	scanf("%d",&k);
	while(k--){
		scanf("%d%d",&m,&n);
		rep[0] = m;
		rotate(m);
		printf("%I64d\n",polya(m,m)%n);
	}
	return 1;
}