Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Happy Birthday, Polycarp!

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputHooray! 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.

Input

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.

Output

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.

Example

Input

6 18 1 9 100500 33 1000000000

Output

10 1 9 45 12 81

Note

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/27/2020 21:03:23 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|