//include //------------------------------------------ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; // typedef //------------------------------------------ typedef long long LL; typedef vector VI; typedef vector VB; typedef vector VC; typedef vector VD; typedef vector VS; typedef vector VLL; typedef vector VVI; typedef vector VVB; typedef vector VVS; typedef vector VVLL; typedef vector VVVI; typedef vector VVVLL; typedef pair PII; typedef pair PLL; typedef pair PIS; typedef pair PSI; typedef pair PSS; typedef vector VPII; typedef vector VPLL; typedef vector VVPII; typedef vector VVPLL; typedef vector VVS; typedef map MII; typedef map MLL; typedef map MSI; typedef map MIS; // container util //------------------------------------------ typedef int pInt[4]; #define ALL(a) (a).begin(),(a).end() #define SZ(a) int((a).size()) #define EACH(i, arr) for(typeof((arr).begin()) i=(arr).begin(); i!=(arr).end(); ++i) #define EXIST(str, e) ((str).find(e)!=(str).end()) #define COUNT(arr, v) count((arr).begin(), (arr).end(), v) #define SEARCH(v, w) search((v).begin(), (v).end(), (w).begin(), (w).end()) #define SORT(c) sort((c).begin(),(c).end()) #define RSORT(c) sort((c).rbegin(),(c).rend()) #define REVERSE(c) reverse((c).begin(), (c).end()) #define ROTATE_LEFT(arr, c) rotate((arr).begin(), (arr).begin()+(c), (arr).end()) #define ROTATE_RIGHT(arr, c) rotate((arr).rbegin(), (arr).rbegin() + (c), (arr).rend()) #define SUMI(arr) accumulate((arr).begin(), (arr).end(), 0) #define SUMD(arr) accumulate((arr).begin(), (arr).end(), 0.) #define SUMLL(arr) accumulate((arr).begin(), (arr).end(), 0LL) #define MULD(arr) accumulate((arr).begin(), (arr).end(), 1., multiplies()) #define UB(arr, n) upper_bound((arr).begin(), (arr).end(), n) #define LB(arr, n) lower_bound((arr).begin(), (arr).end(), n) #define PB push_back #define MP make_pair #define ft first #define sd second // input output //------------------------------------------ #define GL(s) getline(cin, (s)) #define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0) #define OUT(d) std::cout<<(d) #define OUT_L(d) std::cout<<(d)< istream &operator>>(istream &in, pair &p) { in >> p.first >> p.second; return in; } template istream &operator>>(istream &in, vector &v) { for (auto &x: v) in >> x; return in; } template ostream &operator<<(ostream &out, const std::pair &p) { out << "[" << p.first << ", " << p.second << "]" << "\n"; return out; } template inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true; } return false; } //repetition //------------------------------------------ #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i) #define REP(i, n) FOR(i,0,n) #define RREP(i, n) for(int i = n-1;i >= 0;i--) #define FORLL(i, a, b) for(LL i=LL(a);i=LL(a);--i) #define REPLL(i, n) for(LL i=0;i=0;--i) #define FOREACH(x, arr) for(auto &(x) : (arr)) // Option + Control + K Terminal // Command + Control + K Run // Command + b EOF //------------------------------------------ //------------------------------------------ template inline bool ISPRIME(const T x) { if (x <= 1)return false; for (T i = 2; i * i <= x; i++)if (x % i == 0)return false; return true; } template vector DIVISOR(T n) { vector v; for (T i = 1; i * i <= n; ++i) { if (n % i == 0) { v.push_back(i); if (i != n / i) { v.push_back(n / i); } } } sort(v.begin(), v.end()); return v; } template vector> DIVISOR_ALL(T n) { vector> res(n + 1); for (T i = 1; i <= n; i++) { for (T j = i; j <= n; j += i) { res[j].push_back(i); } } return res; } template vector ERATOSTHENES(const T n) { vector arr(n + 1, true); arr[0] = arr[1] = false; for (T i = 2; i * i <= n; i++) { if (arr[i]) { for (T j = i * 2LL; j <= n; j += i) { arr[j] = false; } } } return arr; } template vector ERATOSTHENES_VALUE(const T n) { vector primes = ERATOSTHENES(n); vector results; for (int i = 0; i <= n; i++) if (primes[i]) results.emplace_back(i); return results; } // a <= x < b template vector ERATOSTHENES(const T a, const T b) { vector small = ERATOSTHENES(b); vector prime(b - a, true); for (T i = 2; i * i <= b; i++) { if (small[i]) { for (T j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) { prime[j - a] = false; } } } return prime; } // O(n (logn)^2) template vector SMALLEST_PRIME_FACTORS(T n) { vector spf(n + 1); for (T i = 0; i <= n; i++) spf[i] = i; for (T i = 2; i * i <= n; i++) { if (spf[i] == i) { for (T j = i * i; j <= n; j += i) { spf[j] = i; } } } return spf; } template vector> FACTORIZATION(T x) { vector> ans; for (T i = 2; i * i <= x; i++) { if (x % i == 0) { T count = 0; while (x % i == 0) { count++; x /= i; } ans.push_back(make_pair(i, count)); } } if (x != 1) ans.push_back(make_pair(x, 1)); return ans; } // O(logn) template vector FACTORIZATION(T x, vector &spf) { vector ret; while (x != 1) { ret.push_back(spf[x]); x /= spf[x]; } sort(ret.begin(), ret.end()); return ret; } constexpr LL MAX = 6000000; int main() { auto primes = ERATOSTHENES(MAX); int T; scanf("%d", &T); while (T--) { LL A, P; scanf("%lld %lld", &A, &P); if (primes[P]) { LL s = gcd(A, P); if(s == 1) printf("1") ; else printf("0") ; } else { printf("-1"); } printf("\n"); } }