We call a sequence of n non-negative integers A, awesome if there exists some positive integers x > 1 such that each element Ai in A (where 0 ≤ i < n) is evenly divisible by x. Recall that a evenly divides b if there exists some integer c such that b = a * c.

Given an awesome sequence, A and a positive integer k, find and print the maximum integer L, which satisfies the following conditions:

1. 0 ≤ L ≤ K
2. A ∪ {L} is also awesome. (∪ is the union operator.)

Input

The first line contains the integer t denoting the number of test cases. The next line contains two space-separated positive integers, n (length of the sequence A) and k (the upper bound of answer L).

The third line contains n space separated positive integers describing the elements of A.

Output

For each test case, Print the value of L in a single line (where L is the maximum integer ≤ k and A ∪ {L} is also awesome). As 0 is evenly divisible by any x > 1, there will always be an answer.

Constraints

1 ≤ t ≤ 12

1 ≤ n ≤ 100000

1 ≤ k ≤ 1000000000

1 ≤ Ai ≤ 1000000000

Example

Input:
2
3 5
2 6 4
1 5
7

Output:
4
0