#ifndef _TEMPLATE_ROOT
#define _TEMPLATE_ROOT
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define repl(i, a, b) for(ll i = a; i < (b); ++i)
#define repd(i, a, b) for(int i = b; i >= (a); --i)
#define repdl(i, a, b) for(ll i = b; i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
#endif
#ifndef _TEMPLATE_IO
#define _TEMPLATE_IO

template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void writef(T ...tail) { write(tail...); cout << flush; }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  if (v.size()) {
    rep(i, 0, sz(v) - 1)
      out << v[i] << " ";
    out << v.back();
  }
  return out;
}
#endif
using namespace std;

bitset<5000005> sieve;

ll bm(ll b, ll p, ll m) {
  ll r = 1;
  for (; p; p >>= 1, b = b * b % m) if (p & 1) r = r * b % m;
  return r;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

  sieve.set();
  sieve[0] = sieve[1] = false;

  for (int i = 2; i * i < 5000005; i++)
    for (int j = i * i; j < 5000005; j += i)
      sieve[j] = false;

  int n; read(n);
  rep(i, 0, n) {
    ll a, p; read(a, p);
    a %= p;
    if (!sieve[p])
      write(-1);
    else if (a == 0)
      write(0);
    else
      write(1);
  }
}