Beautiful Palindrome Number

Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

A positive integer x can represent as $(a_1a_2 \ldots a_ka_k \ldots a_2a_1)_{10}$ or $(a_1a_2 \ldots a_{k-1}a_ka_{k-1} \ldots a_2a_1)_{10}$ of a 10-based notational system, we always call x is a Palindrome Number. If it satisfies $0<a_1<a_2< \ldots<a_k \leq 9$, we call x is a Beautiful Palindrome Number.
Now, we want to know how many Beautiful Palindrome Numbers are between 1 and $10^N$.

Input

The first line in the input file is an integer $T(1 \leq T \leq 7)$, indicating the number of test cases.
Then T lines follow, each line represent an integer $N(0 \leq N \leq 6)$.

Output

For each test case, output the number of Beautiful Palindrome Number.

Sample Input

2 1 6

Sample Output

9 258

Hint

heyang

Source

BestCoder Round #13

提交代码