#include<iostream>

 #include <stdlib.h>

 #include <algorithm>

 #include <stdio.h>

 #include<vector>

 using namespace std;

 const int MAXN = 1e5 + ;

 int isprime[MAXN];

 int prime[MAXN];

 int num, n, p;

 void getprime(void){

     num = ;

     for(int i = ; i <= MAXN; i++)if(!isprime[i]){

         prime[num++] = i;

         for(int j = ; j * i <= MAXN; j++){

             isprime[i * j] = ;

         }

     }

 }

 int euler(int x){

     int res = x;

     for(int i = ; i < num && prime[i]*prime[i] <= x; i++){

         if(x % prime[i] == ){

             res = res / prime[i] * (prime[i] - );

             while(x % prime[i] == ){

                 x /= prime[i];

             }

         }

     }

     if(x > ) res = res / x * (x - );

     return res;

 }

 int expmod(int a, int b, int mod){

     int ret = ;

     a = a % mod;

     while(b > ){

         if(b & )ret = (ret * a) % mod;

         a = (a * a) % mod;

         b >>= ;

     }

     return ret;

 }

 int main(void){

     int t;

     getprime();

     scanf("%d", &t);

     while(t--){

         scanf("%d%d", &n, &p);

         int ans = , i;

         for(i = ; i * i < n; i++)if(n % i == ){

             ans = (ans + euler(i) % p * expmod(n, n / i - , p) + euler(n / i) % p * expmod(n, i - , p)) % p;; //这里的i-1代表已经除以整个置换数n了，原本是expmod(n,i)，最后要除以n的，

         }

         if(i * i == n)

             ans = (ans + euler(i) * expmod(n, i - , p)) % p;

         cout << ans << endl;

     }

     return ;

 }