Get Maximum in Generated Array

Given an integer ‘N’. We want to find the maximum element of the array ‘Arr’ of length ‘N’+1 which can be generated as per the following rules:

Arr[0] = 0
Arr[1] = 1
Arr[2 * i] = Arr[i] when 2 ≤ 2 * i ≤ N
Arr[2 * i + 1] = Arr[i] + Arr[i + 1] when 2 ≤ 2 * i + 1 ≤ N

For example:

Suppose ‘N’ = 5, then
Arr[0] = 0
Arr[1] = 1
Arr[2] = Arr[2 * 1] = Arr[1] = 1
Arr[3] = Arr[2 * 1 + 1] = Arr[1] + Arr[2] = 2
Arr[4] = Arr[2 * 2] = Arr[2] = 1
Arr[5] = Arr[2 * 2 + 1] = Arr[2] + Arr[3] = 3

Now we have constructed the ‘Arr’ Array of size ‘N’+1 according to the rules stated in the problem description.
So, Arr = [0, 1, 1, 2, 1, 3] and maximum of its elements is 3.
Hence our output will be 3.

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains a single integer ‘N’, where ‘N’+1 denotes the size of ‘Arr’.

Output Format:

For each test case, print a single integer value denoting the maximum element of ‘Arr’.

Print a separate line for each test case.

Note

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints -

1 ≤ T ≤ 1000
1 ≤ N ≤ 100000
ΣN ≤ 200000

Time limit: 1 Sec