GCDEASY - Easy GCD

no tags 

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 integers 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 U {L} is also awesome. (U is 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 U {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

 

Sample Input

Sample Output

2

3 5

2 6 4

1 5

7

4

0

 


hide comments
himmi97: 2017-05-31 17:26:35

How can Ai be equal to 1.Then it will not be awesome sequence.
Ai should be greater than 1.

himmi97: 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.


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