Read problems statements in Mandarin Chinese and Russian. 

Sereja has an array A of N positive integers : A[1], A[2], A[3], ... , A[N]. 

In a single operation on the array, he performs the following two steps :  

Pick two indices i, j s.t. A[i] > A[j]
A[i] -= A[j]

Sereja can apply these operations any number of times (possibly zero), such that the sum of resulting elements of the array is as small as possible.

Help Sereja find this minimum sum.

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

First line of input contains an integer T - the number of test cases. T test cases follow.

First line of each test case contains the integer N. The next line contains N integers — A[1], A[2], A[3], ... , A[N].

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

For each test case, output a single line with the answer.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A[i] ≤ 10^{9}$

----- Sample Input 1 ------ 
2
1
1
3
2 4 6
----- Sample Output 1 ------ 
1
6
----- explanation 1 ------ 
Example case 2. In this case, one possible way in which Sereja can perform the operations could be as follows. 

Pick i = 2, j = 1. A[2] -= A[1]. Now the resulting array would be [2, 2, 6].
Pick i = 3, j = 2. A[3] -= A[2]. Now the resulting array would be [2, 2, 4].
Pick i = 3, j = 2. A[3] -= A[2]. Now the resulting array would be [2, 2, 2]. 

As the resulting array is [2 2 2], so the sum is 6.

Source: codechef | Difficulty: MEDIUM
Tags: Number theory

Data structures

Mathematics


Solutions:
from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = arr[0]
	for i in range(1, n):
		ans = gcd(ans, arr[i])
	print(ans * n)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = arr[0]
	for i in range(1, n):
		k = arr[i] % ans
		if k != 0 and k < ans:
			ans = k
	print(n * ans)


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


from math import gcd

def snek(k, n):
	ans = k[0]
	for i in k:
		ans = gcd(i, ans)
	ans = ans * n
	print(ans)
for i in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	snek(k, n)


from math import *
from functools import *
t = int(input())
for tc in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = reduce(gcd, l)
	print(x * n)


import sys
import math
import collections
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
for _ in range(ii()):
	n = ii()
	arr = il()
	ans = [arr[0]]
	for l in rg(1, len(arr)):
		ans[0] = math.gcd(ans[0], arr[l])
	ot(n * ans[0])


from math import gcd

def solve(A, N):
	ans = A[0]
	for i in A:
		ans = gcd(i, ans)
	ans = ans * N
	print(ans)
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	solve(A, N)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for i in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	if len(a) == 1:
		print(a[0])
		continue
	ans = gcd(a[0], a[1])
	for j in range(2, len(a)):
		ans = gcd(ans, a[j])
	print(ans * len(a))


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def func(x):
	ans = x[0]
	for i in range(1, n):
		ans = gcd(ans, x[i])
	return ans
for u in range(int(input())):
	n = int(input())
	x = [int(w) for w in input().split()]
	print(n * func(x))


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	for i in arr:
		res = math.gcd(i, res)
	print(res * n)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
for I in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(l[0])
	else:
		g = l[0]
		for I in range(1, n):
			if g > l[I]:
				g = gcd(l[I], g)
			else:
				g = gcd(g, l[I])
		print(n * g)


import math
for _ in range(int(input())):
	num = int(input())
	arr = [int(s) for s in input().split()]
	check = []
	for i in range(len(arr)):
		check.append(math.gcd(arr[i], arr[i - 1]))
	print(min(check) * num)


def gcd(a, b):
	if a == b:
		return b
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) > 1:
		d = gcd(a[0], a[1])
		for i in range(2, n):
			d = gcd(d, a[i])
			if d == 1:
				break
		print(d * n)
	else:
		print(a[0])


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


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = input()
		x = list(map(int, arr.split(' ')))
		result = x[0]
		for y in x:
			result = gcd(y, result)
		print(result * n)

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


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


from math import gcd

def main():
	t = int(input())
	for z in range(t):
		n = int(input())
		li = [int(x) for x in input().split()]
		gd = 0
		for x in li:
			gd = gcd(gd, x)
		ans = n * gd
		print(ans)
main()


def GCD(a, b):
	if a > b:
		(a, b) = (b, a)
	if a == 0:
		return b
	else:
		return GCD(b % a, a)
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	HCF = A[0]
	for i in range(1, N):
		HCF = GCD(A[i], HCF)
	print(HCF * len(A))


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


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


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	if n == 1:
		print(s[0])
	else:
		k = math.gcd(s[0], s[1])
		i = 2
		while i < n:
			k = math.gcd(k, s[i])
			i += 1
		print(k * n)


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


from functools import reduce
from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	print(n * reduce(gcd, l))


import math
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(a[0])
	else:
		ans = math.gcd(a[0], a[1])
		i = 2
		while i < n:
			ans = math.gcd(ans, a[i])
			i += 1
		print(ans * n)


def gcd(l):
	result = l[0]
	for c in l[1:]:
		result = hcf(result, c)
	return result

def hcf(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(gcd(l) * n)


from fractions import gcd
from functools import *

def GCD(A):
	return reduce(gcd, A)
for tests in range(int(input())):
	n = int(input())
	B = [int(i) for i in input().split()]
	g = GCD(B)
	print(g * n)


from fractions import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = -1
	if n > 1:
		g = gcd(a[0], a[1])
		for i in range(2, n):
			g = gcd(g, a[i])
			if g == 1:
				ans = n
				break
		if ans != -1:
			print(ans)
		else:
			print(g * n)
	else:
		print(a[0])


from fractions import gcd
from functools import reduce
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = reduce(gcd, a)
	print(g * n)


from fractions import gcd

def solve(arr, n):
	if n == 1:
		return arr[0]
	g = gcd(arr[0], arr[1])
	for i in range(2, n):
		g = gcd(g, arr[i])
	return n * g
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr, n))