Increasing Numbers

Time limit5sMemory limit256 MB

Summary

For each given number, print -1 unless its digits never decrease, else count smaller integers whose digits never decrease.

Level: Medium6 of 10
Topics: Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

A number is increasing if every digit is greater than or equal to the digit right before it.

Look at these three numbers.

123
101
1111000001111

123 is increasing because $1 < 2 < 3$ . 101 is not increasing, because its second digit 0 is smaller than its first digit 1. 1111000001111 is not increasing either, because its fifth digit 0 is smaller than its fourth digit 1.

Every one-digit number is increasing, and 0 is increasing as well.

Input

The first line contains the number of test cases.

Each test case is one line holding a single natural number. The number has at most 80 digits and its first digit is not 0.

Output

Print one line per test case.

If the given number is not increasing, print -1.

If it is increasing, print how many increasing integers are smaller than it. Counting starts at 0, so 0 belongs to that count.

Every answer fits in a 64-bit integer.

Hint

A number whose digits are all the same is increasing.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
1
1
```
Expected output
```
1
```