题目描述

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

要将一个正整数a四舍五入到最接近的 10^b，其中b为正整数，小王首先找到从右往左数第b个数位。令x为这个数位。 如果 x≥5，小王 将a增加 10^b。

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

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

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

在看了小王的作业后，小洲认为她已经发明了一种新的舍入方式：链式舍入。要链式舍入到最接近的 10^b

小洲将首先舍入到最接近的 10^1

然后舍入到最接近的 10^2

以此类推，直至舍入到最接近的 10^b。

小王认为小洲是错误的，但她太忙于段位晋升，无法确认她的怀疑。她请你计算出存在多少个不小于 2且不超过 N 的整数 x（1≤N≤10^9），使得将 x四舍五入到最接近的 10^P与链式舍入到最接近的 10^P的结果不同，其中 P是满足 10^P≥x的最小整数。

输入格式：

你需要回答多个测试用例。 输入的第一行包含一个整数 T（1≤T≤10^5），为测试用例的数量。以下是 T个测试用例。每个测试用例的输入仅有一行，包含一个整数 N。输入保证同一测试点中的所有 N各不相同。

输出格式：

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

输入样例：

4

1

100

4567

3366

输出样例：

0

5

183

60

样例解释

考虑样例中的第二个测试用例。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相同。

测试点性质：

测试点 2-4：N≤10^3。

测试点 5-7：N≤10^6。

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