题目描述

对于一个正整数，如果它的十进制表示下各位上的数字都相同，则我们称它为一个“特殊数字”，比如：$1,2,99,666,33333333$ 都是特殊数字，而 $101, 2021, 2333$ 都不是特殊数字。

给你一个整数 $n$，求 $1$ 到 $n$ 范围内的所有特殊数字（包括 $1$ 到 $n$）。

输入格式

输入包含多组测试数据。

输入的第一行包含一个整数 $t(1 \le t \le 10^4)$，表示测试数据组数。

接下来 $t$ 行，每行包含一个整数 $n(1 \le n \le 10^9)$。

输出格式

每组测试数据占一行，包含一个整数，表示 $1$ 到 $n$ 范围内特殊数字的个数。

样例

2
5
100

5
18

样例 1 解释

• $1$ 到 $5$ 范围内的特殊数字有：$1,2,3,4,5$；
• $1$ 到 $100$ 范围内的特殊数字有：$1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99$。

数据范围

• 对于 $20\%$ 的数据，$t \le 10, n \le 100$；
• 对于 $40\%$ 的数据，$t \le 100, n \le 1000$；
• 对于 $60\%$ 的数据，$t \le 1000, n \le 10^6$；
• 对于 $100\%$ 的数据，$1 \le t \le 10^4, 1 \le n \le 10^9$。