q = int(input())
mod = 17
for _ in range(q):
    a, b = map(int, input().split())
    ans = 1
    for i in range(mod - 1):
        s = 0
        for j in range(mod):
            s += pow(j, i, mod) * ((b - j) // mod + 1 - (j == 0))
        ans *= pow(s, (a - i) // (mod-1) + 1 - (i == 0))
        ans %= mod
    print(ans)