强迫症

题目描述

冰棍特别喜欢整齐的东西，对于数更是有特殊的癖好。

冰棍认为，如果一个数只有恰好一位不是 $0$，那么这个数是整齐的。比如，$1, 2, 40, 500$ 是整齐的数，而 $1919, 101, 8080$ 不是整齐的数。

现在他很好奇，在 $[1, n]$ 的区间内有多少个这种整齐的数。因为他一天要睡 $25$ 个小时，所以这事交给了你。

输入格式

输入第一行一个整数 $T$。

接下来 $T$ 组数据，每组一行一个整数 $n$。

输出格式

对于每组数据，输出一个整数，表示 $[1, n]$ 内有多少整齐的数。

数据范围

• 对于 $60\%$ 的数据，$n \leq 100$；
• 对于 $100\%$ 的数据，$1 \leq T \leq 10^4$，$1 \leq n \leq 10^6$。

样例数据 1

输入：

4
9
42
100
114

输出：

9
13
19
19