import sys

input = sys.stdin.buffer.readline

MOD = 10 ** 9 + 7


def solve(X, K):
    assert K not in (2, 500000003)
    L = pow(K, -1, MOD - 1)
    return pow(X, L, MOD)


T = int(input())
for _ in range(T):
    print(solve(*map(int, input().split())))