Noora Number

A number is a "Noora" number if the count of distinct digits of the number is equal to the maximum digit of the number. So, 123 is a Noora number but 124 is not. Some of the first Noora numbers are 1, 11, 12, 20, 21, 103, 111, 112, ....

Given $n$, you have to tell how many Noora numbers are smaller or equal to $n$.

Input

Input starts with an integer $T$ ($1 ≤ T ≤ 100000$), denoting the number of test cases. Each case contains an integer $n$ ($1 ≤ n ≤ 10^{18}$).

Output

For each test case, output the number of Noora numbers that are smaller or equal to $n$.

Sample

Input	Output
5 10 100 1000 10000 100000	1 5 29 213 1893