Hill Numbers

A hill number is an integer whose digits may rise and then fall, but never fall and then rise again.

• 12321 is a hill number.
• 101 is not a hill number.
• 1111000001111 is not a hill number.

Two neighboring digits may be equal, before the top or after it. Only integers of 0 or more are counted, and 0 is a hill number.

An integer $N$ is given. If $N$ is a hill number, print how many hill numbers are smaller than $N$. If it is not, print $-1$.

The first line has the number of test cases $T$ ($1 \le T \le 100$).

Each of the next $T$ lines has one integer $N$. $N$ is at least 1 and has at most 70 digits. The answer always fits in a signed 64-bit integer.

Print the answer for each test case on its own line.