万岁!波利卡普已经 $$$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$$$。