#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include "bits/stdc++.h" using namespace std; #define ll long long #define rep(i,n) for(ll i = 0; i < (n); i++) #define endl '\n' const int inf = 1e9 + 11; int MOD = 1e9 + 7; const ll INF = 1LL << 60; bool is_prime(long long n) { // is n prime or not for (long long i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } void solve() { ll a, p; cin >> a >> p; if (is_prime(p)) { if (a % p == 0) { cout << 0 << endl; } else { cout << 1 << endl; } } else cout << -1 << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; rep(_, t) { solve(); } return 0; }