def isPrime(x):
    if x < 2:
        return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True
def sieve(x):
    f = [True]*(x+1)
    f[0], f[1] = False, False

    for i in range(2, len(f)):
        if isPrime(i):
            for j in range(i*2, len(f), i):
                f[j] = False
    return f

t = int(input())
s = sieve(5*10**6)

for i in range(t):
    a,p = map(int,input().split())
    if s[p]:
        print(pow(a,(p-1)//2,p))
    else:
        print(-1)