#include using namespace std; typedef long long ll; typedef pair l_l; typedef pair i_i; 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; } const long long INF = 1e18; //const ll mod = 1000000007; bool IsPrime[10000000]; void solve() { ll A, P; cin >> A >> P; if(!IsPrime[P]) { cout << -1 << endl; return; } if(A % P == 0) cout << 0 << endl; else cout << 1 << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); for(int i = 2; i < 1e7; i++) { IsPrime[i] = true; } for(int i = 2; i < 1e7; i++) { if(!IsPrime[i]) continue; for(int j = i * 2; j < 1e7; j += i) { IsPrime[j] = false; } } ll T; cin >> T; while(T--) solve(); return 0; }