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 ?
The first line of input contains , the number of test cases.
Each test case consists of one line containing a single integer, .
In test file #1:
In test file #2:
In test file #3:
For each test case, output a single line containing a single integer, the number of reversible numbers below .
As mentioned in the problem statement, there are reversible numbers below , the largest of which is .