06745. USACO·连环取整 未做

奶牛 Bessie 回到学校了！她开始做她的数学作业，在作业中她被要求将正整数四舍五入到 $10$ 的幂。

要将一个正整数 $a$ 四舍五入到最接近的 $10^b$，其中 $b$ 为正整数，Bessie 首先找到从右往左数第 $b$ 个数位。令 $x$ 为这个数位。

如果 $x\ge 5$，Bessie 将 $a$ 增加 $10^b$。

然后，Bessie 将从右侧开始直至第 $b$ 个数位的所有数位均设置为 $0$。

例如，如果 Bessie 想要将 $456$ 四舍五入到最接近的 $10^2$（百位），Bessie 会首先找到从右往左数第 $2$ 个数位 $5$。这意味着 $x=5$。然后由于 $x\ge 5$，Bessie 将 $a$ 增加 $100$。最后，Bessie 将 $a$ 中从右侧开始直至第 $2$ 个数位的所有数位设置为 $0$，结果为 $500$。

但是，如果 Bessie 将 $446$ 四舍五入到最接近的 $10^2$，她将得到 $400$。

在看了 Bessie 的作业后，Elsie 认为她已经发明了一种新的舍入方式：链式舍入。要链式舍入到最接近的 $10^b$，Elsie 将首先舍入到最接近的 $10^1$，然后舍入到最接近的 $10^2$，以此类推，直至舍入到最接近的 $10^b$。

Bessie 认为 Elsie 是错误的，但她太忙于数学作业，无法确认她的怀疑。她请你计算出存在多少个不小于 $2$ 且不超过 $N$ 的整数 $x$（$1\le N\le 10^9$），使得将 $x$ 四舍五入到最接近的 $10^P$ 与链式舍入到最接近的 $10^P$ 的结果不同，其中 $P$ 是满足 $10^P\ge x$ 的最小整数。

你需要回答多个测试用例。

输入的第一行包含一个整数 $T$（$1\le T\le 10^5$），为测试用例的数量。以下是 $T$ 个测试用例。

每个测试用例的输入仅有一行，包含一个整数 $N$。输入保证同一测试点中的所有 $N$ 各不相同。

输出 $T$ 行，第 $i$ 行包含第 $i$ 个测试用例的答案。每行包含一个整数，表示存在多少个不小于 $2$ 且不超过 $N$ 的整数在使用两种舍入方法时会得到不同的结果。

【样例解释】

考虑样例中的第二个测试用例。$48$ 应当被计算在内，因为 $48$ 链式舍入到最接近的 $10^2$ 是 $100$（$48\to 50\to 100$），但 $48$ 四舍五入到最接近的 $10^2$ 是 $0$。

在第三个测试用例中，$48$ 和 $480$ 是两个被计算在内的整数。 $48$ 链式舍入到 $100$ 而不是 $0$，$480$ 链式舍入到 $1000$ 而不是 $0$。但是，$67$ 不被计算在内，因为它链式舍入到 $100$，与 $67$ 四舍五入到最接近的 $10^2$ 相同。

• 测试点 5-7：$N\le 10^6$。

• 测试点 8-13：没有额外限制。

【数据规模与约定】

• 测试点 2-4：$N\le 10^3$。

• 测试点 5-7：$N\le 10^6$。

• 测试点 8-13：没有额外限制。

供题：Weiming Zhou