#include<iostream>

 #include<stdio.h>

 #include<algorithm>

 #include<iomanip>

 #include<cmath>

 #include<string>

 #include<vector>

 #define ll __int64

 using namespace std;

 ll euler(int n)

 {

     ll ans=;

     for(int i=;i*i<=n;i++)

     {

         if(n%i==)

         {

             ans*=i-;

             n/=i;

             while(n%i==)

             {

                 ans*=i;

                 n/=i;

             }

         }

     }

     if(n>) ans*=n-;

     return ans;

 }

 ll pows(ll a,ll b,ll m)

 {

     ll ans=;

     while(b)

     {

         if(b&) ans=(ans*a)%m;

         b>>=;

         a=(a*a)%m;

     }

     return ans%m;

 }

 ll cmp(int a,int b,int m)

 {

     ll ans=;

     for(int i=;i<=b;i++)

     {

         ans*=a;

         if(ans>=m) return ans;

     }

     return ans;

 }

 ll fun(int n,int m)

 {

     ll phi=euler(m);

     if(n<) return n;

     ll a=fun(n/,phi);

     ll b=cmp(n%,a,m);

     if(b>=m)

     {

         ll ans=pows(n%,a+phi,m);

         if(ans==)

             ans+=m;

         return ans;

     }

     return b;

 }

 int main()

 {

     int t,i,j,m,n;

     cin>>t;

     while(t--)

     {

         cin>>n>>m;

         ll ans=fun(n,m)%m;

         printf("%I64d\n",ans);

     }

     return ;

 }