#include <iostream>
#include <memory>
#include <cstdlib>
#define M   35005
#define mr 35000
using namespace std;
/*X (X <= 3500),N and P (1 <= N <= 1000000000, 1 <= P <= 30000)*/
int n, p, l=1, pn=0, test;
int prim[10001], notp[M];/*n/logn<15000*/
//prim[]存儲素數(shù)，notp[]用來標(biāo)記素數(shù)，pn用來計數(shù)。 
int prime()
{//線性篩選素數(shù)
	int i, j;
	memset(notp, 0, sizeof(notp));
	for(i = 2; i < mr; i++)
	{
		if(notp[i] == 0)	prim[pn++] = i;
		for(j = 0; prim[j]*i < mr&& j < pn; j++)
		{
			notp[ i*prim[j] ] = 1;
			if(i % prim[j] == 0)	break;//線性的關(guān)鍵體現(xiàn)
		}
	}
      return 0;
}
int phi(int n)
{//線性歐拉函數(shù)，Caclulate,Euler(n)%p.
//Pi為n的質(zhì)數(shù)因子
//n = IIpow(Pi,Ai)
//歐拉公式Euler(n) = II(Pi-1)pow(Pi,Ai-1) = n*II(1-1/Pi) 
	int tem = n, i;
	for(i = 0; i < pn && prim[i]*prim[i] <= tem; i++){
		if(tem % prim[i] == 0)
		{
			n = n - (n/prim[i]);
			do	tem /= prim[i];
			while(tem % prim[i] == 0);
		}
	}
	if(tem != 1) n -= n/tem;
	return n%p;
}
int exp_mod(int m)
{//Calculate n.^m%p.
	int tem, s, ans;
	tem = m;
	ans = 1;
	s = n % p;
	while(tem > 0)
	{
		if(tem % 2 == 1) ans = (ans * s) % p;
		tem /= 2;
		s = (s * s) % p;
	}
	return ans;
}
int main()
{
	prime();//求3500內(nèi)的質(zhì)數(shù)
	scanf("%d",&test);
	while(test--)
	{
		int i, ans=0;
		scanf("%d%d",&n, &p);
		for(l = 1; l*l <= n; l++)
		if(l*l == n)//枚舉循環(huán)長度l，找出相應(yīng)的i的個數(shù)：gcd(i,n)=n/l.
			ans = (ans + phi(l) * exp_mod(l-1)) % p;
		else
		if(n%l == 0)//有長度為l的循環(huán)，就會有長度為n/l的循環(huán)節(jié)。 
			ans = (ans + phi(l) * exp_mod(n/l-1) + phi(n/l) * exp_mod(l-1)) %p;
		printf("%d\n",ans);
	}
	return 0;
}
/*	http://hi.baidu.com/yufuwan1/blog/item/59907a8220427796f603a6b6.html
題目要求：給出兩個整數(shù)n和p，代表n個珠子，n種顏色，要求不同的項鏈數(shù)，并對結(jié)果mod（p）處理。
所屬類型：組合題
應(yīng)用知識：polya，Euler
分析：這題和1286，2409 都有點類似，不同之處在于，只考慮旋轉(zhuǎn)，不考慮翻轉(zhuǎn)；
因此相對前面兩個題目應(yīng)該說是更簡單，但一看數(shù)據(jù)范圍，就不是這么回事了，
1286和2409完全可以直接循環(huán)處理，但這題目n最大達100000000，顯然會TLE，
故需尋求更佳的解決方案。
可以用歐拉函數(shù)進行優(yōu)化，或者用Mobius反演定理進行優(yōu)化。下面講解一下用歐拉優(yōu)化的方法：
旋轉(zhuǎn)：順時針旋轉(zhuǎn)i格的置換中，循環(huán)的個數(shù)為gcd（i，n），每個循環(huán)的長度為n/gcd(i,n)。
如果枚舉旋轉(zhuǎn)的格數(shù)i，復(fù)雜度顯然較高。有沒有好方法呢？可以不枚舉i，反過來枚舉L。
由于L|N,枚舉了L，再計算有多少個i使得0<=i<=n-1并且L＝gcd(i, n)。即gcd（i,n）＝n/L。
不妨設(shè)a＝n/L=gcd(i, n),
不妨設(shè)i＝a*t則當(dāng)且僅當(dāng)gcd(t,L)=1時
Gcd(i,n)=gcd(a*t,a*L)=a。
因為0<=i<n,所以0<=t<n/a=L.
所以滿足這個條件的t的個數(shù)為Euler(L).
現(xiàn)在結(jié)果已經(jīng)很明顯了。Ans＝∑(Euler(L)*(n.^(L-1)))%p。(L為符合上面假設(shè)條件的所有數(shù)）.
復(fù)雜度分析：線性篩選素數(shù)，線性篩選歐拉函數(shù)因子，枚舉L，這些都是在線性的復(fù)雜度內(nèi)完成的。
*/

/*
歐拉函數(shù)的知識見百度百科

至于循環(huán)節(jié)為什么為g(n,i) ,如求1-12的環(huán),轉(zhuǎn)角度數(shù)為　i*360/12,i為轉(zhuǎn)角基數(shù)　＝　５時
1 -- 12 1 -- 12 1 -- 12 1-- 12 1 -- 12 1
當(dāng)繞五圈后走到1處，中間無重復(fù)（？）。n = 12
則 12 / 5 = 2...2	n / i = k...t    即求n與i的最小公倍數(shù) m，所走的點數(shù)為m/i)，
則循環(huán)節(jié)數(shù)為n/(m/i) 即求最大公約數(shù)gcd(n,i);
*/