Lucky Number

发布时间: 2017年12月10日 22:14   最后更新: 2017年12月10日 22:19   时间限制: 1000ms   内存限制: 512M

The 2017 FDU-ICPC contest has started, but Gromah is stuck by a question, so Gromah wants to pick a lucky number and output it directly. Gromah each time will randomly writes an integer k, then find a number that is no more than k and has the largest sum of each digit, which is called the lucky number.

So Gromah wrote T integers k, and he wanted to know what the sum of each digit in the lucky number is for each integer k.

In the first line there is an integer T (T<=1000), which indicates the number of test cases.
In the next T lines there is an integer k (k<=10^9).

For each test case, print the answer in a line.


K = 19260, the lucky number can be 9999, and the sum of each digit is 36.

K = 817, the lucky number can be 799, and the sum of each digit is 25.

2017 fdu-icpc

2017 Fudan ACM-ICPC 程序设计校赛现场赛