题目描述

太棒了！Polycarp 已经 $n$ 岁了！Technocup 团队真诚地祝贺 Polycarp！

Polycarp 庆祝了他所有的 $n$ 个生日：从第 $1$ 岁到第 $n$ 岁。此刻，他在思考：他有多少次过了“美丽的”年龄？

根据 Polycarp 的定义，一个正整数如果只由同一个数字重复一遍或多遍组成，则称为“美丽的”。例如，以下数字是美丽的：$1$、$77$、$777$、$44$ 和 $999999$。以下数字不是美丽的：$12$、$11110$、$6969$ 和 $987654321$。

当然，Polycarp 使用的是十进制数字系统（即进制为 $10$）。

请你帮助 Polycarp 计算，从 $1$ 到 $n$（包含 $n$）中有多少个数字是美丽的。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来有 $t$ 个测试用例。

每个测试用例占一行，包含一个正整数 $n$（$1 \le n \le 10^9$），表示 Polycarp 的年龄。

输出格式

输出 $t$ 个整数，按输入顺序依次给出每个测试用例的答案。每个答案表示从 $1$ 到 $n$（包含 $n$）中美丽的年龄的数量。

说明/提示

在示例的第一个测试用例中，美丽的年龄有 $1$、$2$、$3$、$4$、$5$、$6$、$7$、$8$、$9$ 和 $11$。

由 ChatGPT 4.1 翻译

样例

6
18
1
9
100500
33
1000000000

10
1
9
45
12
81