typedef long long ll; typedef long double ld; #include using namespace std; template< typename T > T mod_pow(T x, T n, const T &p) { T ret = 1; while(n > 0) { if(n & 1) (ret *= x) %= p; (x *= x) %= p; n >>= 1; } return ret; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); ll t; std::cin >> t; for (int di = 0; di < t; di++) { ll a,p; std::cin >> a>>p; bool prime = false; for (int i = 2; i <= sqrt(p); i++) { if(p%i==0){ prime = true; break; } } if(prime){ if(a%p==0){ std::cout << 0 << '\n'; continue; } std::cout << mod_pow(a, p*(p+1)/2, p) << '\n'; }else{ std::cout << -1 << '\n'; } } }