Reduced ID Numbers

T. Chur teaches various groups of students at university U. Every U-student has a unique Student Identification Number (SIN). A SIN $s$ is an integer in the range $0\le s\le \mathit{MaxSIN}$ with $\mathit{MaxSIN}=10^6-1$. T. Chur finds this range of SINs too large for identification within her groups. For each group, she wants to find the smallest positive integer $m$, such that within the group all SINs reduced modulo $m$ are unique.

Input

The first line of input contains the integer $G$ ($1\le G\le 300$): the number of students in the group. The following $G$ lines each contain one SIN. The SINs are distinct, though not necessarily sorted.

Output

Output one line containing the smallest modulus $m$, such that all SINs reduced modulo $m$ are distinct.

Sample Input 1 Sample Output 1
1
124866
1
Sample Input 2 Sample Output 2
3
124866
111111
987651
8