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

t = int(input())

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