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

def main():

    nC = int(input())

    # Process cases.
    for loop in range(nC):

        # Get input.
        toks = input().split()
        p = int(toks[0])
        g = int(toks[1])

        # Check primitive root status and print accordingly.
        if isPrimRoot(p, g):
            print(1)
        else:
            print(0)

# Returns the non-trivial divisors of n.
def getNonTrivialDivisors(n):

    # Add this since I don't start my loop at 1.
    res = [n]

    # Look for divisors.
    i = 2
    while i*i <= n:

        # Found a pair (usually)
        if n%i == 0:

            # We always add this one.
            res.append(i)

            # We usually add its "flip" divisor.
            if i < n//i:
                res.append(n//i)
                
        # Go to next...
        i+=1

    # Return list.
    return res

# Returns True iff g is a primitive root mod p, we are given that p is prime.
def isPrimRoot(p, g):

    # Get all the non-trivial divisors.
    divs = getNonTrivialDivisors(p-1)

    # Check each modular expo. If any are 1, this isn't a primitive root.
    for d in divs:
        if pow(g, (p-1)//d, p) == 1:
            return False

    # If we get here, it is!
    return True

# Run it!
main()