#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using ll = long long;

constexpr ll INF = 1ll<<60;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<class S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

ll T;
bool used[5000010];
std::vector<ll> primes;

void sieve() {
  used[0] = used[1] = true;

  for( ll i = 2; i*i <= 5000000; ++i ) if( !used[i] ) {
    primes.emplace_back( i );

    for( ll j = i; j <= 5000000; j += i )
      used[j] = true;
  }

  return;
}

int main()
{
  sieve();

  scanf( "%lld", &T );

  rep( t, T ) {
    ll A, P;
    scanf( "%lld%lld", &A, &P );

    ll p = *std::lower_bound( all(primes), P );

    if( p != P ) {
      puts("-1");

      continue;
    }

    A %= P;

    if( P > 2 ) {
      printf( "%lld\n", !A ? 0 : 1 );
    } else {
      printf( "%lld\n", A*A%P );
    }
  }

  return 0;
}