LUDIC1 - Ludic Numbers (medium)

Find the number of Ludic numbers less than or equal to $N$.

Input

The first line contains $T$ ($1 \le T \le 1000$), the number of test cases.

Each test case contains a single integer $N$ ($1 \le N \le 10^9$).

Output

For each test case, output the number of Ludic numbers less than or equal to $N$.

Example

Input

10
1
2
3
4
5
10
100
1000
1000000
1000000000

Output

1
2
3
3
4
5
24
142
66164
43956562

Note


Added by:Min_25
Date:2018-04-12
Time limit:25s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2019-12-10 20:53:11
After struggling to post a barely acceptable solution, it was only after trying the harder LUDIC2 problem that I found a respectable answer for this one.

Last edit: 2020-02-24 21:07:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.