题目内容

定义长度为 $L$ 的十进制正整数 $x$ 为渐进普通数，当且仅当存在 $d ∈$ { $1,...,9$ } ，使得 $x$ 满足以下两类之一：

类型 $A： x$ 的 $L$ 个数位都等于 $d$ ；

类型 $B：L≥2，x$ 的前 $L-1$ 个数位都等于 $d$ ，最后一位等于 $d+1$ (因此 $d∈${ $1,...,8$ })。

给定 $n$ ，请统计区间 $[1,n]$ 内渐进普通数的个数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $t(1≤t≤10^4)$ 代表数据组数，每组测试数描述如下：

此后 $t$ 行，每行输入一个整数 $n(1≤n≤10^{18})$ 。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示区间 $[1,n]$ 内渐进普通数的数量。

样例1

输入

3
1
9
100

输出

1
9
26

说明

在这组测试数据中：

当 $n=100$ 时，长度为 $1$ 的类型 $A$ 有 $9$ 个；长度为 $2$ 的类型 $A$ 有 $9$ 个 $(11,22,...,99)$；长度为 $2$ 的类型 $B$ 有 $8$ 个 $(12,23,...,89)$，因此共有 $26$ 个。