GCDEASY - Easy GCD

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

Added by:Jamil Siam
Date:2017-01-12
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2020-03-23 01:14:07
Thinking that this would be easy cost me an hour. Don't get fooled =)
2019-06-19 03:07:09
I am pretty sure I did this correctly :o Can't find any case It's not working properly. Are there some edge cases to watch out for?
2017-05-31 17:26:12
How can Ai be equal to 1.Then it will not be awesome sequence.
Ai should be greater than 1.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.