思路

由于 $n$ 的范围非常大（最高到 $10^{18}$），我们不可能从 1 遍历到 $n$ 来逐个检查每个数是否为渐进普通数，这样做会超时。

注意到渐进普通数的结构非常特殊，它们的数量相对稀少。这启发我们直接生成所有可能的渐进普通数，然后统计其中有多少个小于或等于 $n$。

我们可以按照数字的构成方式来生成它们：

1. 生成所有候选数： 渐进普通数总是由一个基础数字 $d \in \{1, \ldots, 9\}$ 和一个长度 $L$ 决定。

题目内容

定义长度为 $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$ 个。