Maximum Length Even Subarray solution codechef

For Solution
Click Here!
You are given an integer NN. Consider the sequence containing the integers 1,2,…,N1,2,…,N in increasing order (each exactly once). Find the maximum length of its contiguous subsequence with an even sum.
Input Format
 The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
 The first and only line of each test case contains a single integer NN.
Output Format Maximum Length Even Subarray solution codechef
For each test case, print a single line containing one integer — the maximum length of a contiguous subsequence with even sum.
Constraints
 1≤T≤1041≤T≤104
 2≤N≤1042≤N≤104
Subtasks
Subtask #1 (100 points): original constraints
Sample Input 1 Maximum Length Even Subarray solution codechef
3
3
4
5
Sample Output 1
3
4
4
Explanation Maximum Length Even Subarray solution codechef
Example case 1: The optimal choice is to choose the entire sequence, since the sum of all its elements is 1+2+3=61+2+3=6, which is even.
Example case 3: One of the optimal choices is to choose the subsequence [1,2,3,4][1,2,3,4], which has an even sum.