Mason is yet again in danger.

Consider an N digit number A.
let the new number formed by reversing the digits of A be called B .

Mason has to tell that how many N digit numbers A exist such that A + B = 10^N - 1 ?

Note: A should not have any leading zeroes !

Quick. Help. over and out.

Input

First line will contain the number of test cases T , then T lines follow each containing an integer N

Output

For each test case , Print how many N digit numbers exist that satisfy the above equation ,in a new line!

Constraints

1 <= T <= 100
0 <= N <= 10^5

Example
Input:
2
5
2
Output:
0
9

Explanation

When N = 2, one possible number is 18.
A = 18 , Therefore B = 81
Since A + B = 99 .... (10^2 - 1 == 99)
That is, 18+81 = 99, Therefore it is one possible number ..
Can you find the other 8 ?

见题面

见题面