Mysterious Number

Time limit0.25sMemory limit256 MB

Summary
Given N integers, find the largest M for which all N leave equal remainders mod M, or report that no largest M exists.
Level

Medium7 of 10

Topics
Number theory, Math, Greedy, Sorting
Solved
No attempts yet

Problem

Given N nonzero integers, a nonzero integer M is called a mysterious number for the N integers if it satisfies the following property.

  • The remainders when the N integers are divided by M are all equal.

For any N integers, at least one mysterious number exists. For example, 1 is always a mysterious number regardless of the N integers.

Given N numbers, find the largest mysterious number for the N integers.

Input

The first line gives the number of test cases T. Each test case consists of two lines: the first line gives N, and the second line gives N integers.

Output

For each test case, output the largest mysterious number for the N integers. If the mysterious numbers diverge to infinity, output "INFINITY".

Constraints

  • 1 ≤ N ≤ 2,000
  • -109 ≤ N integers ≤ 109

Hint

The remainder when an arbitrary integer p is divided by an arbitrary nonzero integer q is determined by the unique integer a satisfying 0 ≤ p - a×q < q. The remainder is p - a×q.

For example, when p = 7 and q = 3, the remainder is 1; when p = -7 and q = 3, the remainder is 2.

Examples1

  1. Example 1

    Input
    4
5
2 4 6 8 10
5
162 72 54 63 57
5
-20 -30 -50 80 75
4
5 5 5 5
    Expected output
    2
3
5
INFINITY