def extgcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = extgcd(b, a % b)
    return g, y, x - a//b * y


def solve():
    X, K = map(int, input().split())
    _, _, b = extgcd(P-1, K)
    return pow(X, b, P)


P = 10**9 + 7
T = int(input())
for _ in range(T):
    ans = solve()
    print(ans)