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

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

# 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 .