Chef is playing a game on a sequence of N positive integers, say A_{1}, A_{2}, ... A_{N}. The game is played as follows.
If all the numbers are equal, the game ends.
Otherwise
Select two numbers which are unequal
Subtract the smaller number from the larger number
Replace the larger number with the result from above (see the explanation section for clarity)
        
Chef has already figured out that the game always terminates. He also knows, for a given sequence of integers, the game will always terminate on the same value, no matter how the game is played. Chef wants you to simulate the game for him and tell him on which value will the game terminate for a given sequence of integers.

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

The first line of the input contains an integer T, the number of test cases. Then follow the description of T test cases. The first line of each test case contains a single integer N, the length of the sequence. The second line contains N positive integers, each separated by a single space.

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

For each test case, output a single integer - the value of all the numbers when they are equal (and the game terminates), on a line by itself.

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

1 ≤ T ≤ 100
1 ≤ N ≤ 1000
1 ≤ A_{i} ≤ 10^{9}

----- Sample Input 1 ------ 
3
2
10 12
2
5 9
3
6 10 15
----- Sample Output 1 ------ 
2
1
1
----- explanation 1 ------ 
Test Case 1: Since there are only two numbers, the operations are forced.

{ 10, 12 } => Replace 12 with ( 12 - 10 = 2 ) => { 10, 2 }
{ 10, 2 } => Replace 10 with ( 10 - 2 = 8 ) => { 8, 2 }
{ 8, 2 } => Replace 8 with ( 8 - 2 = 6 ) => { 6, 2 }
{ 6, 2 } => Replace 6 with ( 6 - 2 = 4 ) => { 4, 2 }
{ 4, 2 } => Replace 4 with ( 4 - 2 = 2 ) => { 2, 2 }

The value of all the numbers when the game ends is 2.

Test Case 2: Since there are only two numbers, the operations are forced.

{ 5, 9 } => Replace 9 with ( 9 - 5 = 4 ) => { 5, 4 }
{ 5, 4 } => Replace 5 with ( 5 - 4 = 1 ) => { 1, 4 }
{ 1, 4 } => Replace 4 with ( 4 - 1 = 3 ) => { 1, 3 }
{ 1, 3 } => Replace 3 with ( 3 - 1 = 2 ) => { 1, 2 }
{ 1, 2 } => Replace 2 with ( 2 - 1 = 1 ) => { 1, 1 }

The value of all the numbers when the game ends is 1.

Test Case 3: One way to play the game is

{ 6, 10, 15 } => Replace 15 with ( 15 - 6 = 9 ) => { 6, 10, 9 }
{ 6, 10, 9 } => Replace 10 with ( 10 - 6 = 4 ) => { 6, 4, 9 }
{ 6, 4, 9 } => Replace 9 with ( 9 - 6 = 3 ) => { 6, 4, 3 }
{ 6, 4, 3 } => Replace 6 with ( 6 - 4 = 2 ) => { 2, 4, 3 }
{ 2, 4, 3 } => Replace 3 with ( 3 - 2 = 1 ) => { 2, 4, 1 }
{ 2, 4, 1 } => Replace 4 with ( 4 - 2 = 2 ) => { 2, 2, 1 }
{ 2, 2, 1 } => Replace first 2 with ( 2 - 1 = 1 ) => { 1, 2, 1 }
{ 1, 2, 1 } => Replace 2 with ( 2 - 1 = 1 ) => { 1, 1, 1 }

The value of all the numbers when the game ends is 1. You may try to play the game differently and observe that the game will always end when all the values are 1.

Difficulty: EASY
Tags: Number theory

Mathematics

Starter code:

Solutions:
import numpy as np
t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	print(np.gcd.reduce(l))


from math import gcd
t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	flag = 1
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			flag = 0
			break
	if flag == 1:
		print(arr[0])
	else:
		j = arr[0]
		for k in arr:
			j = gcd(j, k)
		print(j)


import numpy as np
for i in range(int(input())):
	y = int(input())
	a = list(map(int, input().split(' ')))
	terminator = np.gcd.reduce(a)
	print(terminator)


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())

def f():
	(n, l) = (IN(), I())
	g = l[0]
	for i in l:
		g = gcd(g, i)
	return g
for _ in range(IN()):
	print(f())


from math import gcd
for tc 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)


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


import math
t = int(input())
for _ in range(0, t):
	n = int(input())
	x = list(map(int, input().split()))
	h = x[0]
	for i in x[1:n + 1]:
		h = math.gcd(h, i)
		if h == 1:
			break
	print(h)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()

	def gcd(a, b):
		if a == 0:
			return b
		else:
			return gcd(b % a, a)
	for i in range(n - 1):
		x = gcd(a[i], a[i + 1])
		a[i] = a[i + 1] = x
	print(x)


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

def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	p = a[0]
	for i in range(1, n):
		p = gcd(p, a[i])
	print(p)
for i in range(int(input())):
	solve()


def find_hcf(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	first_element = a[0]
	second_element = a[1]
	hcf = find_hcf(first_element, second_element)
	for j in range(2, len(a)):
		hcf = find_hcf(hcf, a[j])
	print(hcf)


for _ in range(int(input())):
	import numpy as np
	n = int(input())
	a = list(map(int, input().split()))
	print(np.gcd.reduce(a))


import math
for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	res = num[0]
	for i in range(1, len(num), 1):
		res = math.gcd(res, num[i])
	print(res)


import math
T = int(input())
for i in range(T):
	X = int(input())
	list1 = list(map(int, input().split()))
	d = list1[0]
	for i in range(1, X):
		d = math.gcd(d, list1[i])
	print(d)


from math import gcd

def long(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 = [int(x) for x in input().split()]
	if n == 1:
		print(a[0])
	else:
		print(long(a))


import math
for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	gcd = arr[0]
	for ele in arr:
		gcd = math.gcd(gcd, ele)
		if gcd == 1:
			break
	print(gcd)


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


for i in range(int(input())):
	n = int(input())

	def gcd(a, b):
		if b == 0:
			return a
		else:
			return gcd(b, a % b)
	lst = list(map(int, input().split()))
	res = lst[0]
	for c in lst[1:]:
		res = gcd(res, c)
	print(res)


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(N - 1):
		g = gcd(g, A[i + 1])
	print(g)


import math
for _ in range(int(input())):
	N = int(input())
	A = [int(i) for i in input().split()]
	gcdA = A[0]
	for i in range(1, N):
		gcdA = math.gcd(gcdA, A[i])
	print(gcdA)


import math
T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	L = list(map(int, input().split()))[:N]
	for i in range(N):
		if i == 0:
			ans = math.gcd(L[i], L[i + 1])
		else:
			ans = math.gcd(L[i], ans)
	print(ans)


from math import gcd
for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	g = gcd(L[0], L[1])
	for i in range(2, len(L)):
		g = gcd(g, L[i])
	print(g)


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


import math
for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	gcd = 9999999999
	r = l[0]
	for i in range(a):
		r = math.gcd(r, l[i])
	print(r)


import math

def hcf(d):
	hcf = a[0]
	for i in d:
		hcf = math.gcd(hcf, i)
	return hcf
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}.fromkeys(a)
	if len(d) == 1:
		print(a[0])
	else:
		print(hcf(d))


t = int(input())
import math
for i in range(t):
	n = int(input())
	arr = input().split(' ')
	for j in range(n):
		arr[j] = int(arr[j])
	m = math.gcd(arr[0], arr[1])
	if m == 1:
		print(1)
	else:
		for x in range(2, n):
			m = math.gcd(m, arr[x])
			if m == 1:
				print(1)
				break
		else:
			print(m)


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


from math import gcd

def main():
	for _ in range(int(input())):
		n = int(input())
		A = list(map(int, input().split(' ')))[:n]
		ans = A[0]
		for i in A:
			ans = gcd(ans, i)
		print(ans)
main()


def gcd(y, z):
	while z != 0:
		(y, z) = (z, y % z)
	return y
for _ in range(int(input())):
	num = int(input())
	nums = list(map(int, input().split()))
	res = nums[0]
	for i in range(1, num):
		res = gcd(res, nums[i])
	print(res)


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

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


import math

def GCD(a, b):
	if b == 0:
		return a
	return GCD(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in range(1, len(l)):
		g = GCD(g, l[i])
	print(g)


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


import numpy as np
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(np.gcd.reduce(l))


from math import gcd
from functools import reduce
for _ in range(int(input())):
	n = int(input())
	arr = set(map(int, input().split()))
	if len(arr) == 1:
		print(arr[0])
	else:
		res = reduce(lambda a, b: gcd(a, b), arr)
		print(res)


import math
t = int(input())
for tc in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = l[0]
	for j in l:
		a = math.gcd(a, j)
		if a == 1:
			break
	print(a)


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	result = nums[0]
	for i in range(1, n):
		result = gcd(result, nums[i])
	print(result)


def hcf(a, b):
	if a < b:
		(a, b) = (b, a)
	while a % b != 0:
		a = a % b
		(a, b) = (b, a)
	else:
		return b
for i in range(int(input())):
	input()
	l = list(map(int, input().split()))
	if len(l) == 1:
		print(l[0])
	else:
		if l[0] == l[1]:
			h = l[0]
		else:
			h = hcf(l[0], l[1])
		for j in l[2:]:
			h = hcf(j, h)
		print(h)


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


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


t = int(input())
import math
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	h = l[0]
	hcf = 0
	for x in range(1, n):
		hcf = math.gcd(h, l[x])
		h = hcf
	print(hcf)
	t -= 1


def gcd(a, b):
	rem = b % a
	b = a
	a = rem
	if rem == 0:
		return b
	return gcd(a, b)
t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	gc = arr[0]
	for i in arr[1:]:
		gc = gcd(gc, i)
	print(gc)


import numpy
t = int(input())
while t:
	n = int(input())
	l = sorted(list(map(int, input().split())))
	print(numpy.gcd.reduce(l))
	t -= 1


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)
for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	ans = l1[0]
	for i in range(1, len(l1)):
		ans = gcd(ans, l1[i])
	print(ans)


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	flag = 0
	r = l[0]
	for i in range(len(l)):
		r = math.gcd(r, l[i])
	print(r)


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