Project Euler #145: How many reversible numbers are there below one-billion?

_{This problem is a programming version of Problem 145 from projecteuler.net}

Some positive integers have the property that the sum consists entirely of odd (decimal) digits. For instance, and . We will call such numbers reversible; so , , , and are reversible. Leading zeroes are not allowed in either or .

There are 120 reversible numbers below one-thousand.

Given , how many reversible numbers are there below ?

Input Format

The first line of input contains , the number of test cases.

Each test case consists of one line containing a single integer, .

Constraints

In test file #1:
In test file #2:
In test file #3:

Output Format

For each test case, output a single line containing a single integer, the number of reversible numbers below .

Sample Input

2
1000
948

Sample Output

120
119

Explanation

As mentioned in the problem statement, there are reversible numbers below , the largest of which is .