1277A.md (1596B)
1 Source: https://codeforces.com/problemset/problem/1277/A 2 3 A. Happy Birthday, Polycarp! 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Hooray! Polycarp turned $n$ years old! The Technocup Team sincerely congratulates Polycarp! 22 23 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? 24 25 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$. 26 27 Of course, Polycarpus uses the decimal numeral system (i.e. radix is 10). 28 29 Help Polycarpus to find the number of numbers from $1$ to $n$ (inclusive) that are beautiful. 30 31 Input 32 33 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. 34 35 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. 36 37 Output 38 39 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. 40 41 Example 42 43 Input 44 45 ``` 46 6 47 18 48 1 49 9 50 100500 51 33 52 1000000000 53 ``` 54 55 Output 56 57 ``` 58 10 59 1 60 9 61 45 62 12 63 81 64 ``` 65 66 Note 67 68 In the first test case of the example beautiful years are $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$ and $11$.