408500: GYM103158 E AKA AKA learns number theory
Description
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.
InputThe 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).
OutputFor 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.
ExampleInput2 9 1 890 1 2 3 4 5 6 7 8 9 5 1 66 2310 96577 33263 82861 190747Output
887 64Note
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).