Ramp Number.md

Ramp Number

A Ramp Number is a number whose digits only rise or stay the same; they never fall.

• 123 is a ramp number.
• 101 is not a ramp number.
• 1111000001111 is not a ramp number.

Given a positive integer n, if it is a ramp number, print the number of ramp numbers less than it. If it is not a ramp number, print -1.

Input

Input will start with a single line giving the number of test cases. Each test case will be a single positive integer on a single line, with up to 80 digits. The result will always fit into a 64-bit long.

Output

For each test case, print -1 if the input is not a ramp number. Print the number of ramp numbers less than the input value if the input value is a ramp number.

Sample Input

5
11
123
101
1111
99999

Sample Output

10
65
-1
220
2001