06630. USACO·链式舍入 未做

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

要把正整数 $a$ 四舍五入到最接近的 $10^b$（$b$ 为正整数），Bessie 先找到从右往左数第 $b$ 个数位，记为 $x$：

• 若 $x\ge 5$，Bessie 把 $a$ 增加 $10^b$；
• 然后，Bessie 把 $a$ 中从右往左数第 $b$ 位及其右侧的所有数位都变为 $0$。

例如，把 $456$ 四舍五入到最接近的 $10^2$：第 $2$ 个数位是 $5$，$x=5\ge 5$，于是先加 $100$，再把第 $2$ 位及其右侧清零，得到 $500$。而把 $446$ 这样处理会得到 $400$。

Elsie 发明了一种新的舍入方式——链式舍入：要链式舍入到最接近的 $10^b$，先舍入到最接近的 $10^1$，再舍入到最接近的 $10^2$，以此类推，直到舍入到最接近的 $10^b$。

请统计：在 $2$ 到 $N$（$1\le N\le 10^9$）的整数中，有多少个 $x$ 满足「把 $x$ 直接四舍五入到最接近的 $10^P$」与「把 $x$ 链式舍入到最接近的 $10^P$」的结果不同，其中 $P$ 是满足 $10^P\ge x$ 的最小整数。

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

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

输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案。

【样例解释】

• 第二个测试用例中，$48$ 应当被计入：$48$ 链式舍入到 $10^2$ 的结果是 $100$（$48\to 50\to 100$），但直接舍入到 $10^2$ 的结果是 $0$。
• 第三个测试用例中，$48$ 和 $480$ 都被计入：$48$ 链式舍入到 $100$ 而非 $0$；$480$ 链式舍入到 $1000$ 而非 $0$。而 $67$ 不被计入，因为它链式舍入到 $100$，与直接舍入到 $10^2$ 的结果相同。

【数据规模与约定】

共 13 个测试点。

【出处】USACO 2024 December Contest, Bronze, Problem 1「Roundabout Rounding」（本站题面采用 USACO 官方中文翻译）。