408500: GYM103158 E AKA AKA learns number theory

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.

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 ≤ 10⁸), the length of the array and the interval for the number X.

The second line contains N integers A₁, A₂, ... , A_N (1 ≤ A_i ≤ 10⁸).

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.

2
9 1 890
1 2 3 4 5 6 7 8 9
5 1 66
2310 96577 33263 82861 190747

887
64

Least Common Multiple LCM of multiple arguments is computed recursively according to the equation LCM(X₁, X₂, ... , X_N) = LCM(LCM(X₁, X₂, ... , X_N - 1), X_N).