#include using namespace std; typedef long long ll; #define pb push_back #define fi first #define se second typedef pair P; using VP = vector

; using VVP = vector; using VI = vector; using VVI = vector; using VVVI = vector; const int inf = 1e9 + 7; const ll INF = 1LL << 61; const ll mod = 1e9 + 7; template inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int i, j; int m = 5050505; vector prime(m, 1); for (i = 2; i < m; i++) { for (j = 2; i * j < m; j++) prime[i * j] = 0; } int t; cin >> t; while (t--) { ll a, p; cin >> a >> p; if (prime[p]) { if (a % p == 0) cout << 0; else cout << -1; } else cout << 1; cout << endl; } }