Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given an array A[ ] and the lenght of the array is N. Intially, array A[ ], is constructed with permutation of N.
For example,
If N is 3, then array A[ ] = {1,2,3} .
If N is 4, then array A[ ] = {1,2,3,4}.
If N is 5, then array A[ ] = {1,2,3,4,5}.
You can rearrange this array A[ ]. After rearrange you can do following of the operations,

• Divide array A[ ] into maximum subarray
• Each subarray has equal length
• Each subarray has at least two elements.
• Each subaray, different between Maximum and minimum element should be equal for all. For example,
  A[] ={1,3,4,2}, we can divide it, two subarray : {1,3}, {4,2}.
  Different subarray {1,3} , Max element - Min element = 3 - 1 = 2 ;
  Different subarray {4,2} , Max element - Min element = 4 - 2 = 2 ;

Find the maximum partition of the array after ful-fill the above conditions.

Input

First Line T, the number of test cases.
In each test case, an integer N.

\(1 < = T < = 10^4\)
\(2 < = N < = 10^9\)

Output

In each test case, print the maximum partition of the array.

Sample

2
4
3

2
1

Sample test explaination :
First test case, N = 4 that means intially array A[] = { 1, 2, 3, 4} .
We can rearrange it, A[] = { 1, 3, 2, 4 }.
After rearrange we can divide it two subarray, {1 , 3} and {2 , 4}. Both subarray has equal length.
Subarray {1,3} difference , Max - Min = 3 - 1 = 2;
Subarray {2,4} difference , Max - Min = 4 - 2 = 2;
both subarray difference has equal.
So answer is maximum two subarray possible.

Second test case, N = 3, intially array A[] = { 1,2,3};
only way possible to take whole array as a subarray. So answer is 1.