B. Cascading Sums
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For a positive integer $$$x$$$, define the cascading sum of $$$x$$$ as the sum of all of $$$x$$$'s nonempty prefixes.

For example, the cascading sum of $$$2023$$$ is $$$2023+202+20+2=2247$$$.

You are given $$$q$$$ queries, where each query gives you a positive integer $$$n$$$. For each query, output the number of positive integers $$$m$$$ such that $$$m \le n$$$ and $$$m$$$ is not the cascading sum of any number.

Input

The first line consists of an integer $$$q$$$, the number of queries ($$$1 \leq q \leq 10^5$$$). The description of the queries follows.

The first line of each query contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^{18})$$$.

Output

For each query, output the number of positive values which are not cascading sums and are at most $$$n$$$.

Example
Input
5
4
10
220
3000
3500
Output
0
1
21
299
349
Note

For the first query, $$$m = 1, 2, 3, 4$$$ are all cascading sums. For example, $$$3$$$ is the cascading sum of $$$3$$$. Therefore, there are $$$0$$$ values.

For the second query, $$$10$$$ is the only value which is not a cascading sum, so there is $$$1$$$ value.

Problem Credits: Anonymous Red Panda