You are given an array A_{1}, A_{2}, \dots, A_{N} of length N. You can perform the following operation any number of times (possibly 0 times) :
Choose any two indices i and j and replace either A_{i} or A_{j} with \gcd(A_{i},A_{j}).

Find the minimum possible sum (ie. A_{1} + A_{2} + \dots + A_{N}) that you can achieve, and output that.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first line of each test case contains an integer N - the length of the array A.
- The second line of each test case contains N space-separated integers A_{1},A_{2},\ldots,A_{N}.
​

------ Output Format ------ 

For each test case, output on a new line the minimum sum of the array that can be achieved.

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

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $3 * 10^{5}$.

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
2
2
5 10
3
2 2 6

----- Sample Output 1 ------ 
10
6

----- explanation 1 ------ 
Test case $1$: Choose $i=1,j=2$ and replace $A_{2}$ with $\gcd(5,10)=5$.

Test case $2$: Choose $i=1,j=3$ and replace $A_{3}$ with $\gcd(2,6)=2$.

Source: codechef | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in range(1, n):
		g = math.gcd(g, l[i])
	print(n * g)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = a[0]
	for x in a:
		g = math.gcd(g, x)
	print(n * g)


from math import gcd
t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	a = gcd(l[0], l[1])
	for i in range(2, n):
		a = gcd(a, l[i])
	print(a * n)


from math import gcd

def gcd_arr(arr):
	g = gcd(arr[0], arr[1])
	for i in range(2, len(arr)):
		g = gcd(g, arr[i])
	return g
for _ in range(int(input())):
	n = int(input())
	a = gcd_arr([int(x) for x in input().split()])
	print(a * n)


import math
a = int(input(''))
for i in range(a):
	t = int(input(''))
	h = [int(x) for x in input('').split()]
	k = list(h)
	k.sort()
	j = k[0]
	for g in k:
		j = math.gcd(j, g)
	print(j * t)


import math
t = int(input())
while t > 0:
	n = int(input())
	l = sorted(list(map(int, input().split())))
	res = l[0]
	for j in l:
		res = math.gcd(res, j)
	print(n * res)
	t -= 1


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	res = l[0]
	for j in l:
		res = gcd(res, j)
	print(n * res)


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	res = l[0]
	for j in l:
		res = math.gcd(res, j)
	print(n * res)


def getgcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	new = 0
	change = 1
	while change == 1:
		a.sort()
		for i in range(n - 1):
			change = 0
			new = getgcd(a[i], a[i + 1])
			if a[i + 1] != new:
				a[i + 1] = new
				change = 1
	print(sum(a))


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	res = a[0]
	for i in a:
		res = math.gcd(res, i)
	print(res * n)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	x = l[0]
	for i in l:
		x = math.gcd(x, i)
	print(x * n)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[0]
	for i in a:
		b = math.gcd(b, i)
	print(n * b)


import numpy as np
t = int(input())
for i in range(t):
	n = int(input())
	a = np.array(list(map(int, input().split())))
	p = np.gcd.reduce(a)
	print(n * p)


import numpy as np
t = int(input())
while t > 0:
	n = int(input())
	a = np.array(list(map(int, input().split())))
	p = np.gcd.reduce(a)
	print(p * n)
	t -= 1


from math import gcd

def mn(b):
	b.sort()
	for w in range(1, len(b)):
		b[w] = gcd(b[0], b[w])
	return b
T = int(input())
for i in range(0, T):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = []
	while True:
		if c == a:
			break
		else:
			c = tuple(a)
			a = mn(a)
			c = list(c)
	sm = 0
	for w in range(0, len(c)):
		sm += c[w]
	print(sm)


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


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	mini = 10 ** 13
	for i in range(n - 1):
		gcd = math.gcd(a[i], a[i + 1])
		mini = min(mini, gcd)
	print(mini * len(a))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	arr = [int(j) for j in input().split()]
	res = arr[0]
	for i in range(1, n):
		res = gcd(res, arr[i])
	print(res * n)


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

def aa(a, n):
	g = a[0]
	for i in range(1, n):
		g = gcd(g, a[i])
	print(n * g)
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	aa(a, n)


def gcd(a, b):
	if b > a:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mi = min(arr)
	g = arr[0]
	for ele in arr:
		g = gcd(g, ele)
	mi = min(g, mi)
	ans = mi * n
	print(ans)


from math import gcd

def minimumgcd(arr, n):
	g = arr[0]
	for i in range(0, n):
		g = gcd(g, arr[i])
	return g
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	lowgcd = minimumgcd(arr, n)
	print(n * lowgcd)
	t -= 1


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	gcd = arr[0]
	for j in arr:
		gcd = math.gcd(gcd, j)
	print(gcd * length)


import math
t = int(input())
while t > 0:
	n = int(input())
	l = [int(i) for i in input().split()]
	r = l[0]
	for i in l[1:]:
		r = math.gcd(r, i)
	print(n * r)
	t -= 1


import math
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	res = A[0]
	for i in A[1:]:
		res = math.gcd(res, i)
	print(res * N)


from math import gcd
ans = []
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	an = A[0]
	for a in A[1:]:
		an = gcd(a, an)
	ans.append(N * an)
print(*ans, sep='\n')


ans = []

def gcd(a, b):
	return gcd(b, a % b) if a % b else b
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	an = A[0]
	for a in A[1:]:
		an = gcd(a, an)
	ans.append(N * an)
print(*ans, sep='\n')


from math import gcd
n = int(input())
for i in range(n):
	p = int(input())
	a = list(map(int, input().split()))
	for i in range(p):
		a[0] = gcd(a[0], a[i])
	print(a[0] * p)


import sys
import math
input = sys.stdin.readline

def gcd(x, y):
	r = x % y
	if r == 0:
		return y
	else:
		return gcd(y, r)
T = int(input())
for _ in range(T):
	n = int(input())
	L = list(map(int, input().split()))
	A = L[0]
	for i in range(1, n):
		A = gcd(A, L[i])
	print(A * n)


from math import gcd
n = int(input())
for i in range(n):
	x = int(input())
	a = list(map(int, input().split()))
	for j in range(1, x):
		a[0] = gcd(a[0], a[j])
	print(a[0] * x)


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
T = int(input())
for _ in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	v = L[0]
	for i in range(1, N):
		v = gcd(v, L[i])
	print(v * N)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	mingcd = float('inf')
	for i in range(0, n - 1):
		if arr[i] == 1:
			temp = 1
			break
		temp = math.gcd(arr[i], arr[i + 1])
		if temp == 1:
			break
		arr[i + 1] = temp
		mingcd = min(mingcd, temp)
	if temp == 1:
		print(n)
	else:
		print(n * mingcd)


def gcd(a, b):
	if a == b:
		return a
	elif a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(b, a % b)
	else:
		return gcd(b % a, a)
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	k = a[0]
	for i in range(1, n):
		k = gcd(k, a[i])
	print(k * n)
	t -= 1


import math
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	num1 = arr[0]
	num2 = arr[1]
	gcd = math.gcd(num1, num2)
	for j in range(2, len(arr)):
		gcd = math.gcd(gcd, arr[j])
	print(gcd * N)


from math import *
v = int(input())
for i in range(v):
	a = int(input())
	l = list(map(int, input().split()))
	gcd_min = 1000000000
	for i in range(a - 1):
		b = gcd(l[i], l[i - 1])
		gcd_min = min(gcd_min, b)
	print(gcd_min * a)


import math
T = int(input())
for _ in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	mini = float('inf')
	idx = 0
	for (i, val) in enumerate(l):
		if val < mini:
			mini = val
			idx = i
	flag = False
	res = mini
	x = mini
	for (i, val) in enumerate(l):
		if i != idx:
			a = math.gcd(mini, val)
			x = min(x, a)
	print(x * len(l))


def gcd(x, y):
	if x > y:
		while x % y != 0:
			b = x % y
			x = y
			y = b
		return y
	else:
		while y % x != 0:
			b = y % x
			y = x
			x = b
		return x
t = int(input())
for i in range(t):
	n = int(input())
	li = list(map(int, input().strip().split()))
	a = sorted(li)
	gc = gcd(a[0], a[1])
	if a[0] == 1:
		print(n)
	else:
		for m in a[2:]:
			gc = gcd(gc, m)
		print(n * gc)


from math import *
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = 0
	for j in range(n):
		b = gcd(b, a[j])
	print(b * n)


from math import gcd
test_cases = int(input())
for t in range(test_cases):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		c = gcd(c, a[i])
	print(c * n)


import math
test_case = int(input())
for i in range(test_case):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	gc = 0
	for i in range(n):
		gc = math.gcd(gc, arr[i])
	print(gc * n)


def gcd(A, B):
	if A % B == 0:
		return B
	return gcd(B, A % B)
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = A[0]
	for i in range(1, N):
		if A[i] >= ans:
			ans = gcd(A[i], ans)
		else:
			ans = gcd(ans, A[i])
	print(ans * N)


import math
for cc in range(int(input())):
	length = int(input())
	a = list(map(int, input().split()))
	gcd = a[0]
	for i in range(length - 1):
		gcd = math.gcd(gcd, a[i + 1])
	print(gcd * length)


import math

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	num1 = l[0]
	num2 = l[1]
	gcd = find_gcd(num1, num2)
	for i in range(2, len(l)):
		gcd = find_gcd(gcd, l[i])
	print(gcd * n)


import math

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()))
	res = l[0]
	for i in range(len(l)):
		res = gcd(res, l[i])
	print(N * res)


def findgcd(x, y):
	if y == 0:
		return x
	else:
		return findgcd(y, x % y)
T = int(input())
arr = []
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	num1 = arr[0]
	num2 = arr[1]
	gcd = findgcd(num1, num2)
	for i in range(2, len(arr)):
		gcd = findgcd(gcd, arr[i])
	print(gcd * N)


def gcd(m, n):
	if n == 0:
		return m
	else:
		return gcd(n, m % n)
for t in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	res = l[0]
	for i in range(len(l)):
		res = gcd(res, l[i])
	print(N * res)


import math
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = arr[0]
	for i in range(n - 1):
		res = math.gcd(res, arr[i + 1])
	print(res * n)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = arr[0]
	for i in range(n - 1):
		res = gcd(res, arr[i + 1])
	print(res * n)


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = a[0]
	for i in range(1, n):
		c = math.gcd(c, a[i])
	print(n * c)


import math
for i in range(int(input())):
	le = int(input())
	l = list(map(int, input().split()))
	gcd = math.gcd(l[0], l[1])
	for j in range(2, le):
		gcd = math.gcd(gcd, l[j])
	print(gcd * le)