Dividing the Students

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
In the city of "M", there are N girls who attend a certain high school. Historically, all of the students of this school are divided into two groups, not necessarily equal in size, right before they start to study.
Each girl in the city of "M" has an integer ID number A_{i}, that somehow corresponds to her interests, ideology and beliefs. Each girl is unique, so each ID is unique as well.
Some of the girls have similar interests. For any pair of girls, say the ith and the jth one, we call the value of similarity the number min(A_{i}^{Aj} mod (10^{9}+7), A_{j}^{Ai} mod (10^{9}+7)).
The teachers have decided that they want the students in each group to be as diverse as possible. This way they will be encouraged to become acquainted and make friends faster. For this reason they want to divide the students in such a way that the maximal similarity value of any two girls' IDs in the same group is as small as possible.
Please help them and find the minimal possible maximal similarity value of two girls' IDs within a single group after the optimal division.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case starts with a single integer N  the number of students.
Then, there is a line containing N spaceseparated integers A_{1}, A_{2}, ..., A_{N}  the IDs of the girls.
Output
For each test case output a single line with a single integer  the answer to the problem.
Constraints
 1 ≤ T ≤ 1000
 1 ≤ A_{i} ≤ 10^{9}
Subtasks
Example
Input: 1 4 1 2 1024 1025 Output: 1048576
Explanation
The first and the fourth girl will form the first group; the second and the third will form the second group.
Author:  xcwgf666 
Tester:  white_king 
Editorial  http://discuss.codechef.com/problems/DIVIDE 
Tags  binary, bipartite, easy, graph, ltime18, xcwgf666 
Date Added:  11112014 
Time Limit:  1  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 