#include using namespace std; #define REP(i, n) for (ll i = 0; i < n; i++) #define REPR(i, n) for (ll i = n; i >= 0; i--) #define FOR(i, m, n) for (ll i = m; i < n; i++) #define FORR(i, m, n) for (ll i = m; i >= n; i--) #define REPO(i, n) for (ll i = 1; i <= n; i++) #define ll long long #define INF (ll)1 << 60 #define MINF (-1 * INF) #define ALL(n) n.begin(), n.end() #define MOD 1000000007 #define P pair bool IsPrime(ll n) { if (n <= 1)return false; for (ll i = 2; i <= sqrt(n); i++) { if (n % i == 0)return false; } return true; } vector era(ll n) { vector ok(n + 1, true); ok[0] = false; ok[1] = false; vector res; for (ll i = 2; i <= sqrt(n); ++i) { if (IsPrime(i)) { for (ll j = i * i; j <= n; j += i) ok[j] = false; } } FOR(i, 2, n + 1)if (ok[i])res.push_back(i); return ok; } vector s = era(10000000); int main() { ll t; cin >> t; REP(i, t){ ll a, v; cin >> a >> v; if(!s[v]){ printf("%d\n", -1); continue; } printf("%d\n", a % v != 0); } }