C. 小菜学数学II

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

众所周知，小菜特别喜欢数学。这天，他突发奇想，定义了一个新函数 $S$ 。

$S$ 的定义如下:

$S(5) = 5, S(11) = 2, S(587) = 20 ...$

如果能够满足

$S(X) > S(X + 1)$

小菜就将 $X$ 定义为Vegetablenumber。

现在小菜想考一考你，给定一个正整数 $N$ ，询问 $[1, N]$ 中有多少个满足定义的X。

输入格式

输入第一行包含一个正整数 $T$ ， $1 <= T <= 1000$ ，代表小菜的问题个数。

接下来包含T行，每一行一个正整数 $N$ ， $1 <= N <= 10^{12}$ 。

打印T个正整数，每一行对应询问的答案。

0
1
58