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

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, .

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, .

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, .

As increases, the proportion of bouncy numbers below increases such that there are only numbers below one-million that are not bouncy and only non-bouncy numbers below .

How many numbers below are not bouncy?

As the answer can be large, print the result mod

**Input Format**

First line contains an integer which is the number of tests, next lines contain an integer .

**Constraints**

**Sample Input**

```
3
3
5
10
```

**Sample Output**

```
474
4953
277032
```