Sharan, the brave boy, is currently standing at the origin (0,0). He is taking part in The Game of Two. In each round of this game, he is given an integer n and he is asked to reach (n,0) in minimum number of jumps.
There are a few of rules of this game. They are :
Sharan, though a brave boy, is not smart enough.
Can you please help him figure out the minimum number of jumps he needs to reach his goal ?
The first line contains a single integer q, number of rounds. (1 <= q <= 105).
Then q lines follow. Each of them contains an integer n. (1 <= n <= 109).
Output contains q lines.
ith line contains the minimum number of jumps needed in the ith round.
Input | Output |
---|---|
3 8 11 15 | 1 3 2 |
8 = 23
11 = 23 + 22 - 20
15 = 24 - 21