Happy Birthday, Polycarp!

题意翻译

称一个数为美丽的数，当且仅当这个数中每个数码相同。 如 $1,77,44,9999$ 就是美丽的数， $10,28$ 就不是美丽的数。 求 $[1,n]$ 中美丽的数的个数。 多测，共 $T$ 组测试数据。

题目描述

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.

输入输出样例

输入样例 #1

6
18
1
9
100500
33
1000000000

输出样例 #1

10
1
9
45
12
81

说明

In the first test case of the example beautiful years are $ 1 $ , $ 2 $ , $ 3 $ , $ 4 $ , $ 5 $ , $ 6 $ , $ 7 $ , $ 8 $ , $ 9 $ and $ 11 $ .