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 .