#费马定理和快速幂
# b * b^(p-2) = 1 mod p
#如果b是p的倍数，两个不互质，无解

def qmi(a,k,p):
    res = 1
    while k:
        if k & 1:               #如果当前k末尾是1
            res = res * a % p   #那么乘以上一次运算a的平方 (a^k%p)
        k >>= 1                 #每次算完，删掉末尾k（二进制）
        a = a * a % p           #每次把a平方 (a^k%p)

    return res

if __name__ =='__main__':
    n = int(input())

    for i in range(n):
        a, p = map(int,input().split())
        res = qmi(a, p-2, p)
        print(res if a % p != 0 else 'impossible')