Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Alexey is trying to develop a program for a very simple microcontroller. It makes readings from various sensors over time, and these readings must happen at specific regular times. Unfortunately, if two of these readings occur at the same time, the microcontroller freezes and must be reset. 

There are N different sensors that read data on a regular basis. For each i from 1 to N, the reading from sensor i will occur every A_{i} milliseconds with the first reading occurring exactly A_{i} milliseconds after the microcontroller is powered up. Each reading takes precisely one millisecond on Alexey's microcontroller.

Alexey wants to know when the microcontroller will freeze after he turns it on.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line contains single integer N denoting the number of sensors.

The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting frequency of measurements. Namely, sensor i will be read every A_{i} milliseconds with the first reading occurring A_{i} milliseconds after the microcontroller is first turned on.

------ Output ------ 

For each test case, output a single line containing the number of milliseconds until the microcontroller freezes.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$2 ≤ N ≤ 500$
$1 ≤ A_{i} ≤ 10^{9}$
 
------ Subtasks ------ 

Subtask #1 (10 points) 1  ≤ T ≤ 10, 2 ≤ N ≤ 9, 1 ≤ A_{i} ≤ 500
Subtask #2 (20 points) 1  ≤ T ≤ 10, 2 ≤ N ≤ 500, 1 ≤ A_{i} ≤  1000
Subtask #3 (70 points)  original constraints
 
----- Sample Input 1 ------ 
3
3
2 3 5
4
1 8 7 11
4
4 4 5 6
----- Sample Output 1 ------ 
6
7
4
----- explanation 1 ------ 
Case 1: in 6 milliseconds, the third reading will be attempted from the 1st sensor and the second reading will be attempted from the 2nd sensor.
Case 2: in 7 milliseconds the seventh reading will be attempted from the 1st sensor and the first reading will be attempted from the 3rd sensor.
Case 3: in 4 milliseconds, the first readings from the first two sensors will be attempted.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	min_lcm = -1
	for i in range(N):
		for j in range(N):
			if i == j:
				continue
			l = lcm(L[i], L[j])
			if l < min_lcm or min_lcm == -1:
				min_lcm = l
	print(min_lcm)


def compute_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def compute_lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm
t = input()
for c in range(0, int(t)):
	n = int(input())
	l1 = list(map(int, input().split()))
	mini = 1e+18
	for j in range(0, len(l1)):
		for k in range(j + 1, len(l1)):
			mini = min(compute_lcm(l1[j], l1[k]), mini)
	print(mini)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	freeze = -1
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			l = lcm(a[i], a[j])
			if l < freeze or freeze == -1:
				freeze = l
	print(freeze)


from sys import maxsize
from math import gcd

def lcm(a: int, b: int) -> int:
	return a * b // gcd(a, b)
for _ in range(int(input())):
	n = int(input())
	sensors = list(map(int, input().split()))
	min_lcm = maxsize
	for i in range(n - 1):
		for j in range(i + 1, n):
			min_lcm = min(lcm(sensors[i], sensors[j]), min_lcm)
	print(min_lcm)


from math import gcd

def lcm(x, y):
	return x * y // gcd(x, y)
for _ in range(int(input())):
	n = int(input())
	res = 9223372036854775807
	l = list(map(int, input().split()))
	for i in range(n - 1):
		for j in range(i + 1, n):
			res = min(res, lcm(l[i], l[j]))
	print(res)


from math import gcd
import sys
inf = 10 ** 20

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	x = int(input())
	ans = inf
	l = list(map(int, input().split()))
	for i in range(x - 1):
		for j in range(i + 1, x):
			ans = min(ans, lcm(l[i], l[j]))
	print(ans)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def lcm(a, b):
	return abs(a * b) // gcd(a, b)
T = int(input())
for x in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	an = lcm(a[0], a[1])
	for i in range(n - 1):
		if a[i] < an:
			for j in range(i + 1, n):
				if lcm(a[i], a[j]) < an:
					an = lcm(a[i], a[j])
		else:
			break
	print(an)


import math

def l(a, b):
	return a * b // math.gcd(a, b)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for j in range(n - 1):
		for k in range(j + 1, n):
			b += [l(a[j], a[k])]
	print(min(b))


from math import gcd
from sys import maxsize
for _ in range(int(input())):
	n = int(input())
	time = list(map(int, input().split()))
	mi_gcd = maxsize
	for i in range(n):
		for j in range(i + 1, n):
			mi_gcd = min(mi_gcd, time[i] * time[j] // gcd(time[i], time[j]))
	print(mi_gcd)


from math import gcd
for _ in range(int(input())):
	lcm = lambda a, b: a * b // gcd(a, b)
	N = int(input())
	A = [int(s) for s in input().split()]
	print(min((lcm(A[i], A[j]) for i in range(N) for j in range(i))))


import math
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	l = []
	arr.sort()
	for i in range(n - 1):
		for j in range(i + 1, n):
			l.append(arr[i] * arr[j] // math.gcd(arr[i], arr[j]))
	print(min(l))


from math import gcd

def lcm(x, y):
	r = x * y // gcd(x, y)
	return r
t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	m = lcm(a[0], a[1])
	for i in range(n - 1):
		for k in range(i + 1, n):
			v = lcm(a[i], a[k])
			m = min(m, v)
	print(m)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for t in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l1.sort()
	f = 2 ** 100
	for i in range(n):
		for j in range(i + 1, n):
			f = min(f, lcm(l1[i], l1[j]))
	print(f)


def get_hcf(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def get_lcm(a, b):
	return a * b // get_hcf(a, b)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	minn = get_lcm(arr[0], arr[1])
	for i in range(n - 1):
		for j in range(i + 1, n):
			var2 = get_lcm(arr[i], arr[j])
			minn = min(minn, var2)
	print(minn)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	lcm = a * b // gcd(a, b)
	return lcm
t = int(input())
for i in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	mini = 1e+18
	for j in range(0, len(m)):
		for k in range(j + 1, len(m)):
			mini = min(lcm(m[j], m[k]), mini)
	print(int(mini))


import math
t = int(input().strip())
for i in range(0, t):
	n = int(input().strip())
	ans = 10000000000000000000000000000000000000000000
	arr = input().strip().split()
	for i in range(0, n):
		arr[i] = int(arr[i])
	for k in range(n):
		for j in range(k + 1, n):
			lcmm = arr[k] * arr[j] // math.gcd(arr[k], arr[j])
			ans = min(ans, lcmm)
	print(ans)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
T = int(input())
for tj in range(T):
	N = int(input())
	frequencies = list(map(int, input().split()))
	min_v = 10 ** 18 + 1
	for i in range(N):
		for j in range(i + 1, N):
			lcm = frequencies[i] * frequencies[j] // gcd(frequencies[i], frequencies[j])
			min_v = min(lcm, min_v)
	print(min_v)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 20

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = inf
	for i in range(n):
		for j in range(i + 1, n):
			ans = min(ans, lcm(l[i], l[j]))
	print(ans)


from math import *

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = inf
	for i in range(n):
		for j in range(i + 1, n):
			ans = min(ans, lcm(l[i], l[j]))
	print(ans)


def gcd(x, y):
	while x > 0:
		(x, y) = (y % x, x)
	return y
for _ in range(int(input())):
	n = int(input())
	x = sorted(list(map(int, input().split())))
	ans = 1e+18
	for i in range(n - 1):
		if ans < x[i]:
			break
		for j in range(i + 1, n):
			if ans < x[j]:
				break
			temp = gcd(x[i], x[j])
			temp = x[i] * x[j] // temp
			if temp < ans:
				ans = temp
	print(ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	s = []
	for j in range(n):
		for k in range(j + 1, n):
			s.append(l[j] * l[k] // math.gcd(l[j], l[k]))
	print(min(s))


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	a = []
	for i in range(n):
		for j in range(i + 1, n):
			a.append(l[i] * l[j] // math.gcd(l[i], l[j]))
	print(min(a))


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for i in range(n):
		for j in range(i + 1, n):
			k = l[i] * l[j] // gcd(l[i], l[j])
			l1.append(k)
	print(min(l1))


def hcf(a, b):
	if b == 0:
		return a
	return hcf(b, a % b)
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	p = a[0] * a[1] // hcf(a[0], a[1])
	mi = p
	for i in range(n):
		for j in range(i + 1, n):
			p = a[i] * a[j] // hcf(a[i], a[j])
			if mi > p:
				mi = p
	print(mi)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for i in range(n):
		for j in range(i + 1, n):
			p = l[i] * l[j] // gcd(l[i], l[j])
			l1.append(p)
	print(min(l1))


t = int(input())

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(t):
	n = int(input())
	a = [int(v) for v in input().split()]
	minLcm = 10000000000 ** 2 + 1
	for i in range(n - 1):
		for j in range(i + 1, n):
			lcm = a[i] * a[j] // gcd(a[i], a[j])
			if lcm < minLcm:
				minLcm = lcm
	print(minLcm)


def HcmLcm(a, b):
	if a == b:
		return a
	else:
		c = a
		d = b
		while b % a > 0:
			r = b % a
			b = a
			a = r
		return c * d // a
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	l = []
	for i in range(n - 1):
		for j in range(i + 1, n, 1):
			l.append(HcmLcm(a[i], a[j]))
	l.sort()
	print(l[0])


import sys
from math import gcd
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]

def LCM(a, b):
	return a * b // gcd(a, b)
for _ in range(RI()):
	lens = RI()
	arrs = RMI()
	ans = int(10 ** 18) + 10
	for i in range(lens):
		for j in range(i + 1, lens):
			ans = min(ans, LCM(arrs[i], arrs[j]))
	print(ans)


from math import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = []
	for i in range(len(l1)):
		for j in range(i + 1, len(l1)):
			l2.append(lcm(l1[i], l1[j]))
	l2.sort()
	print(l2[0])


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def LCM(a, b):
	return a * b // gcd(a, b)

def Multiples(Freqs, N):
	List = []
	for i in range(N - 1):
		for j in range(i + 1, N):
			List.append(LCM(Freqs[i], Freqs[j]))
	List.sort()
	return List
for _ in range(int(input())):
	N = int(input())
	Freqs = [int(s) for s in input().split()]
	Freqs.sort()
	least = Multiples(Freqs, N)
	print(least[0])


def gcd(m, n):
	if n == 0:
		return m
	else:
		return gcd(n, m % n)
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = pow(10, 20)
	for j in range(1, n):
		for x in range(0, j):
			temp = l[j] * l[x] // gcd(l[j], l[x])
			if m > temp:
				m = temp
	print(m)


import math

def lcm(a, b):
	return a * b // math.gcd(a, b)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 1e+19
	for i in range(n):
		for j in range(i + 1, n):
			ans = min(ans, lcm(a[i], a[j]))
	print(ans)


def hcf(a, b):
	if b == 0:
		return a
	return hcf(b, a % b)

def lcm(a, b):
	return a * b // hcf(a, b)
t = int(input())
while t:
	t -= 1
	n = int(input())
	lt = list(map(int, input().split()))
	ans = 1e+19
	for i in range(n):
		for j in range(i + 1, n):
			ans = min(ans, lcm(lt[i], lt[j]))
	print(ans)


from math import gcd
test_case = int(input())
for i in range(test_case):
	size = int(input())
	elements = list(map(int, input().split()))
	empty = []
	for j in range(size - 1):
		for k in range(j + 1, size):
			lcm = elements[j] * elements[k] // gcd(elements[j], elements[k])
			empty.append(lcm)
	print(min(empty))


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for j in range(n - 1):
		for k in range(j + 1, n):
			lcm = a[j] * a[k] // math.gcd(a[j], a[k])
			b.append(lcm)
	print(min(b))


import math

def lcm(a, b):
	l = a * b // math.gcd(a, b)
	return l
t = int(input())
for i in range(0, t):
	n = int(input())
	k = [int(n) for n in input().split()]
	li = []
	for i in range(0, n - 1):
		for j in range(i + 1, n):
			l = lcm(k[i], k[j])
			li.append(l)
	print(min(li))


import math
from itertools import combinations

def lcm(pair):
	return pair[0] * pair[1] // math.gcd(pair[0], pair[1])
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	pairs = list(combinations(arr, 2))
	res = min(pairs, key=lcm)
	print(lcm(res))


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().strip().split()))[:n]
	LCM = []
	i = 0
	for j in range(i, n):
		for k in range(n):
			if j == k:
				pass
			else:
				LCM.append(A[j] * A[k] // gcd(A[j], A[k]))
	print(min(LCM))


from itertools import combinations
from functools import lru_cache

@lru_cache(None)
def gcd(a, b):
	if a > 0:
		return gcd(b % a, a)
	return b

@lru_cache(None)
def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	n = int(input())
	res_arr = []
	inp_arr = [int(i) for i in input().strip().split()]
	for tup in combinations(inp_arr, 2):
		res_arr.append(lcm(*sorted(tup)))
	print(min(res_arr))