// Arup Guha
// 10/24/2024
// Solution to CIS 3362 Hmk#5 Problem 9

/*** Note: C solutions won't work past about 10^9... ***/

#include <stdlib.h>
#include <stdio.h>

// Put all function prototypes here.
int isPrimRoot(long long p, long long g);
long long fastModExpo(long long b, long long e, long long m);
long long* getNonTrivialDivisors(long long p, int* numDiv);

int main() {

    int n;
    scanf("%d", &n);

    for (int loop=0; loop<n; loop++) {

        long long p, g;
        scanf("%lld%lld", &p, &g);

        if (isPrimRoot(p, g))
            printf("1\n");
        else
            printf("0\n");

    }

    return 0;
}

int isPrimRoot(long long p, long long g) {

    // Get all of the divisors of p-1.
    int numD = 0;
    long long* divs = getNonTrivialDivisors(p-1, &numD);

    // Go thorough each non-trivial divisor. If any of these modular exponents is 1, we have proof g
    // isn't a primitive root.
    for (int i=0; i<numD; i++) {
        int d = divs[i];
        long long tmp = fastModExpo(g, (p-1)/d, p);
        if (tmp == 1) return 0;
    }

    // Clean up.
    free(divs);

    // If we get here, we're good.
    return 1;
}

// Returns b to the power e mod m.
long long fastModExpo(long long b, long long e, long long m) {

    // Base case.
    if (e == 1) return b%m;

    // Savings for even case.
    if (e%2 == 0) {
        long long tmp = fastModExpo(b, e/2, m);
        return (tmp*tmp)%m;
    }

    // Regular breakdown.
    return (fastModExpo(b, e-1, m)*b)%m;
}

// Returns all divisors of p > 1
long long* getNonTrivialDivisors(long long p, int* numDiv) {

    // Store answers here.
    long long* vals = calloc(10000, sizeof(long long));

    // Go up to square root looking for divisors.
    int idx = 0;
    for (long long i=2; i*i<=p; i++) {
        if (p%i == 0) {
            vals[idx++] = i;
            if (i < p/i) vals[idx++] = p/i;
        }
    }

    // Add this because I didn't before.
    vals[idx++] = p;

    vals = realloc(vals, sizeof(long long)*idx );
    *numDiv = idx;
    return vals;
}