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 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 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
nadstratosfer: 2020-03-23 01:14:07

Thinking that this would be easy cost me an hour. Don't get fooled =)

jpietras: 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?

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