from math import gcd
for _ in range(int(input())):
    ans = 0
    n = int(input())
    for x in range(10 ** (n - 1),10 ** (n)):
        s = str(x)
        flag = 0
        for n in range(len(s) - 2):
            if gcd(int(s[n]), int(s[n + 1])) == gcd(int(s[n + 2]), int(s[n + 1])):
                flag = 1
        if not flag:
            ans += 1
            # print(x)
    print(ans % int(1e9 + 7))