#include <bits/stdc++.h>

using namespace std;
using ll = long long;
int main() {
    int T;cin >> T;
    auto f = [&](ll x){
        if(x == 1)return 0;
        for(int i = 2;i*i<=x;i++)if(x%i==0)return 0;
        return 1;
    };
    while(T--){
        ll A, P;cin >> A >> P;
        if(f(P))cout << (!!(A%P)) << endl;
        else cout << -1 << endl;

    }

}