import java.util.*;
import java.io.*;

public class Main {
	public static int phi(int n){
		int ans=n;
		for(int i=2;i*i<=n;++i){
			if(n%i==0){
				ans=ans/i*(i-1);
				while(n%i==0){
					n/=i;
				}
			}
		}
		if(n>1){
			ans=ans/n*(n-1);
		}
		return ans;
	}
	public static int Quick_Pow(int x,int p,int MOD){
		if(p==0){
			return 1;
		}
		int ans=Quick_Pow(x,p>>1,MOD);
		ans=(ans*ans)%MOD;
		if((p&1)==1){
			ans=(x%MOD*ans)%MOD;
		}
		return ans;
	}
	public static void main(String[] argc){
		int T,n,P;
		Scanner sc = new Scanner (new BufferedInputStream(System.in));
		T=sc.nextInt();
		for(int zu=1;zu<=T;++zu){
			int ans=0;
			n=sc.nextInt();
			P=sc.nextInt();
			for(int i=1;i*i<=n;++i){
				if(n%i==0){
					ans=(ans+((phi(n/i)%P)*Quick_Pow(n,i-1,P))%P)%P;
//					System.out.printf("Test:%d\n",ans);
					if(i*i!=n){
						ans=(ans+((phi(i)%P)*Quick_Pow(n,n/i-1,P))%P)%P;
//						System.out.printf("Test:%d\n",ans);
					}
				}
			}
			System.out.println(ans);
		}
		sc.close();
    }
}