Problem Description

Assume that f(0) = 1 and 0^0=1. f(n) = (n%10)^f(n/10) for all n bigger than zero. Please calculate f(n)%m. (2 ≤ n , m ≤ 10^9, x^y means the y th power of x).

 

Input

The first line contains a single positive integer T. which is the number of test cases. T lines follows.Each case consists of one line containing two positive integers n and m.

 

Output

One integer indicating the value of f(n)%m.

 

Sample Input

 

Sample Output

 

 #include <iostream>

 #include<cstdio>

 using namespace std;

 #define ll long long

 ll phi(ll c)

 {

     ll ans = c;

     for(int i = ; i*i <= c; i++) {

         if(c%i == ){

             ans -= ans/i;

             while(c%i == ) c /= i;

         }

     }

     if(c > ) ans -= ans/c;

     return ans;

 }

 ll quick_mod(ll a, ll b, ll mod)

 {

     if(a >= mod) a = a%mod + mod;   // 并不是直接%mod

     ll ans = ;

     while(b){

         if(b&){

             ans = ans*a;

             if(ans >= mod) ans = ans%mod + mod;　　//**

         }

         a *= a;

         if(a >= mod) a = a%mod + mod;　　//**

         b >>= ;

     }

     return ans;

 }

 ll solve(ll n, ll m)

 {

     ll p = phi(m);

     if(n == ) return ;

     ll index = solve(n/, p);

     return quick_mod(n%, index, m);

 }

 int main()

 {

     ll n, m, T;

     cin >> T;

     while(T--){

         scanf("%I64d%I64d", &n, &m);

         printf("%I64d\n", solve(n,m)%m);

     }

     return ;

 }