def inv(k):
    res = pow(k, 5*10**8 + 1, 5*10**8 + 3)
    if res % 2 == 0:
        res += 5*10**8 + 3
        res %= 10**9 + 6
    return res

def solve(x, k):
    return pow(x, inv(k), 10**9 + 7)

t = int(input())
for i in range(t):
    x, k = map(int, input().split())
    print(solve(x, k))