E. AKA AKA learns number theory
time limit per test
1.5 seconds
memory limit per test
64 megabytes
input
lcm.in
output
standard output

Some years ago, AKA AKA team lost ACPC champion title after failing to solve a number theory problem (ACPC2018 G). This year, AKA AKA team are giving you a number theory problem to prepare for the CPC.

Given an integer array A. Find an integer X between L and R that would maximize the LCM of A after inserting X in a.

Input

The first line of the input contains one integer T (1 ≤ T ≤ 100) the number of test cases.

Each test case consists of two lines:

First line contains three numbers N, L, and R (1 ≤ N ≤ 777, 1 ≤ L ≤ R ≤ 108), the length of the array and the interval for the number X.

The second line contains N integers A1, A2, ... , AN (1 ≤ Ai ≤ 108).

Output

For each test case, output one integer X (L ≤ X ≤ R) that maximizes the LCM of the array a after inserting X in a. If there are multiple answers, output the largest one.

Example
Input
2
9 1 890
1 2 3 4 5 6 7 8 9
5 1 66
2310 96577 33263 82861 190747
Output
887
64
Note

Least Common Multiple LCM of multiple arguments is computed recursively according to the equation LCM(X1, X2, ... , XN) = LCM(LCM(X1, X2, ... , XN - 1), XN).