← 返回题目列表

Codeforces · 1277/A

A. 生日快乐,波利卡普!

中文机器翻译题面 查看原题

万岁!波利卡普已经 $$$n$$$ 岁了! Technocup团队衷心祝贺Polycarp!

坡旅甲庆祝了他所有的 $$$n$$$ 生日:从 $$$1$$$ 到第 $$$n$$$。此刻他在想:自己漂亮了多少年了?

根据 Polycarp 的说法,如果一个正整数仅由一位重复一次或多次的数字组成,那么它就是美丽的。例如,以下数字很漂亮:$$$1$$$、$$$77$$$、$$$777$$$、$$$44$$$ 和 $$$999999$$$。以下数字并不漂亮:$$$12$$$、$$$11110$$$、$$$6969$$$ 和 $$$987654321$$$。

当然,Polycarpus 使用十进制数字系统(即基数为 10)。

帮助Polycarpus找出从$$$1$$$到$$$n$$$(含)之间漂亮的数字的数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例由一行组成,其中包含一个正整数 $$$n$$$ ($$$1 \le n \le 10^9$$$) — Polycarp 已经转动了多少年。

输出

打印 $$$t$$$ 整数 — 按照测试中写入的顺序给出给定测试用例的答案。每个答案都是一个整数:$$$1$$$ 和 $$$n$$$(含)之间的美好年份数。

示例

输入 #1

6
18
1
9
100500
33
1000000000

输出 #1

10
1
9
45
12
81

注意

在示例的第一个测试用例中,美丽的岁月是 $$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$、$$$5$$$、$$$6$$$、$$$7$$$、$$$8$$$、$$$9$$$ 和 $$$11$$$。