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();

    }

}