Problem A
I Hate The Number Nine

How many positive $d$ digit numbers exist that do not contain a nine?

Input

The first line of the input consists of a single integer, $T$, the number of test cases.
Each of the following $T$ cases consists of a single integer $d$, the number of digits.

• $1\le T\le 20$

• $1\le d\le {10}^{18}$

Output

For each test case, output the number of positive numbers with $d$ digits that do not contain a nine. Since this number can be very large, output it modulo $1000000007$.

3
1
2
100

8
72
343393926