#include <iostream>

using lint = long long;

void solve() {
    lint a;
    int p;
    std::cin >> a >> p;

    for (int i = 2; i * i <= p; ++i) {
        if (p % i != 0) continue;

        std::cout << -1 << "\n";
        return;
    }

    std::cout << (a % p != 0) << "\n";
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int q;
    std::cin >> q;
    while (q--) solve();

    return 0;
}