Student ID Numbers

Time limit1sMemory limit128 MB

Summary

Given up to 300 distinct student IDs under 10^6, find the smallest modulus m so that all IDs have distinct remainders mod m.

Level: Medium4 of 10
Topics: Brute force, Math, Number theory
Solved: No attempts yet

Problem

Every student entering Z University receives a student ID number. Each ID is an integer between $0$ and $10^6 - 1$ inclusive, and no two students share the same ID.

Professor Sang-geun Kim tells his students apart by their ID numbers. To remember them more easily, he wants to find the smallest positive integer $m$ such that, when every student's ID is divided by $m$ , all of the resulting remainders are distinct.

For each test case, determine this smallest $m$ .

Input

The first line contains the number of test cases $N$ .

Each test case begins with a line containing the number of students $G$ that the professor teaches ( $1 \le G \le 300$ ). The next $G$ lines each contain one student's ID. No two students have the same ID.

Output

For each test case, print on its own line the smallest positive integer $m$ such that all of the students' IDs give distinct remainders when divided by $m$ .

Examples1

Example 1
Input
```
2
1
124866
3
124866
111111
987651
```
Expected output
```
1
8
```