A13108 | Happy Birthday, Polycarp!

Hooray! Polycarp turned $n$ years old! The Technocup Team sincerely congratulates Polycarp!

Polycarp celebrated all of his $n$ birthdays: from the $1$ -th to the $n$ -th. At the moment, he is wondering: how many times he turned beautiful number of years?

According to Polycarp, a positive integer is beautiful if it consists of only one digit repeated one or more times. For example, the following numbers are beautiful: $1$ , $77$ , $777$ , $44$ and $999999$ . The following numbers are not beautiful: $12$ , $11110$ , $6969$ and $987654321$ .

Of course, Polycarpus uses the decimal numeral system (i.e. radix is 10).

Help Polycarpus to find the number of numbers from $1$ to $n$ (inclusive) that are beautiful.

The first line contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases in the input. Then $t$ test cases follow.

Each test case consists of one line, which contains a positive integer $n$ ( $1 \le n \le 10^9$ ) — how many years Polycarp has turned.

Print $t$ integers — the answers to the given test cases in the order they are written in the test. Each answer is an integer: the number of beautiful years between $1$ and $n$ , inclusive.