Yet Another Array Partition

Yet Another Array Partition

সময় লিমিট: 1.0 s

মেমরি লিমিট: 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

Input Output
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.

Information

ID
1052
Difficulty
8
Category
Math | Number_Theory দেখানোর জন্য ক্লিক করুন
Tags
# Submissions
161
Accepted
24
Accepted Ratio
15%
Uploaded By

Related

In following contests:

Brain Booster #3