Contents

• For Solution

Nishant does pretty weird stuff. Today, he wants to create a weird sequence.

According to Nishant, a sequence AA of length NN is called weird if:

• N3N≥3

• 2Ai>Ai1+Ai+1 i{2,3,4….,N1}2⋅Ai>Ai−1+Ai+1 ∀i∈{2,3,4….,N−1}

Nishant wants to construct a long weird sequence to impress his weird friends, but there’s a problem: he only knows how to count up to KK, so the sequence can only contain integers in the range [1,K][1,K].

Help Nishant determine the length of the longest weird sequence he can construct using only integers from 11 to KK.

Help Nishant solution codechef

• The first line contains a single integer TT denoting the number of testcases. The description of TT testcases follows.
• The first and only line of each testcase contains a single integer KK.

Output Format

For each testcase, print one line containing a single integer – the maximum length of a weird sequence which can be obtained using only integers in [1,K][1,K].

Help Nishant solution codechef

• 1T1051≤T≤105
• 2K1092≤K≤109

Sample Input 1

3
3
5
1073


Help Nishant solution codechef

4
6
92


Help Nishant solution codechef

Test Case 11: One possibl e weird sequence is {1,3,3,2}{1,3,3,2}. It can be shown that there is no weird sequence with length >4>4.

Test Case 22: One possible weird sequence is {2,4,5,5,4,1}{2,4,5,5,4,1}. It can be shown that there is no weird sequence with length >6>6.