题目详情
返回题库题目描述
奶牛 Bessie 回到学校了！她开始做她的数学作业，在作业中她被要求将正整数四舍五入到 10 的幂。
要将一个正整数 a 四舍五入到最接近的 $ 10^b $ ，其中 b 为正整数，Bessie 首先找到从右往左数第 b 个数位。令 x 为这个数位。 如果 x≥5 ，Bessie 将 a 增加$ 10^b $。
然后，Bessie 将从右侧开始直至第 b 个数位的所有数位均设置为 0 。 例如，如果 Bessie 想要将 456 四舍五入到最接近的$ 10^2 $（百位），Bessie 会首先找到从右往左数第 2 个数位 5 。这意味着 x=5 。然后由于 x≥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 \leq N \leq 10^9 $ ），使得将 x 四舍五入到最接近的$ 10^P $与链式舍入到最接近的$ 10^P $的结果不同，其中 P 是满足$ 10^P \geq N $的最小整数。
输入描述
你需要回答多个测试用例。
输入的第一行包含一个整数T（$ 1 \leq T \leq 10^5 $），为测试用例的数量。以下是T个测试用例。
每个测试用例的输入仅有一行，包含一个整数N。输入保证同一测试点中的所有N各不相同。
数据范围：
- 测试点 2-4：$ N \leq 10^3 $
- 测试点 5-7：$ N \leq 10^6 $
- 测试点 8-13：没有额外限制。
输出描述
输出 T 行，第 i 行包含第 i 个测试用例的答案。每行包含一个整数，表示存在多少个不小于 2 且不超过 N 的整数在使用两种舍入方法时会得到不同的结果。
提示
考虑样例中的第二个测试用例。48 应当被计算在内，因为 48 链式舍入到最接近的 $ 10^2 $ 是 100 （48→50→100 ），但 48 四舍五入到最接近的$ 10^2 $是 0 。 在第三个测试用例中，48 和 480 是两个被计算在内的整数。 48 链式舍入到 100 而不是 0 ，480 链式舍入到 1000 而不是 0 。但是，67 不被计算在内，因为它链式舍入到 100 ，与 67 四舍五入到最接近的$ 10^2 $相同。