Help Nishant solution codechef

Help Nishant solution codechef

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.

Input Format

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].

Constraints

Help Nishant solution codechef

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

Sample Input 1 

3
3
5
1073

Sample Output 1

Help Nishant solution codechef

4
6
92

Explanation

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.

Leave a Comment