阿克去登山，他发现在健步道上走了一段距离后会看见提示步数的告示牌。告示牌上显示的步数只有一种形式：

i × 1 0 j ( 1 ⩽ i ⩽ 9 ) i×10 j (1⩽i⩽9)

其中 i , j i,j 都是整数。如果一个位置距离健步道起点需要的步数满足上述形式，就一定会有告示牌提醒。

阿克从地图上知道了从起点到终点的步数，他想知道沿途能看到的按从起点到终点顺序所有告示牌数量。

输入格式 本题包含多组测试数据。

输入的第一行包含一个正整数 T T，表示测试数据的组数。

每组数据只有一行，包含一个字符串 n n，表示从起点到终点的步数。保证字符串是十进制意义下的正整数。

输出格式 输出 T T 行，每行输出一个数，表示沿途能看到的告示牌数量。

input1
复制代码
10
56904
715
9905
72198
2290
315
143
9734
154
1128
output1
复制代码
41
25
36
43
29
21
19
36
19
28
数据范围
对于
100% 的数据，保证 1 ⩽ T ⩽ 10 1⩽T⩽10， 3 ⩽ ∣ n ∣ ⩽ 1 0 5 3⩽∣n∣⩽10 5 。

数据点编号 ∣ n ∣ ⩽ ∣n∣⩽ 1 ∼ 2 1∼2 5 5 3 ∼ 4 3∼4 18 18 5 ∼ 10 5∼10 1 0 5 10 5