While at Kira's house, Josuke saw a piece of paper on the table with a task written on it.

The task sounded as follows. There is an array $a$ of length $n$. On this array, do the following:

select an integer $k > 1$;

split the array into $k$ subsegments $^\dagger$;

calculate the sum in each of $k$ subsegments and write these sums to another array $b$ (where the sum of the subsegment $(l, r)$ is ${\sum_{j = l}^{r}a_j}$);

the final score of such a split will be $\gcd(b_1, b_2, \ldots, b_k)^\ddagger$.

The task is to find such a partition that the score is maximum possible. Josuke is interested in this task but is not strong in computer science. Help him to find the maximum possible score.

$^\dagger$ A division of an array into $k$ subsegments is $k$ pairs of numbers $(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$ such that $l_i \le r_i$ and for every $1 \le j \le k - 1$ $l_{j + 1} = r_j + 1$, also $l_1 = 1$ and $r_k = n$. These pairs represent the subsegments.

$^\ddagger$ $\gcd(b_1, b_2, \ldots, b_k)$ stands for the greatest common divisor (GCD) of the array $b$.


-----Input-----

The first line contains a single number $t$ ($1 \le t \le 10^4$) — the number of test cases.

For each test case, the first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, a_3, \ldots, a_n$ ($1 \le a_i \le 10^9 $) — the array $a$ itself.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print a single integer — the maximum score for the optimal partition.


-----Examples-----

Input
6
4
2 2 1 3
2
1 2
3
1 4 5
6
1 2 1 1 1 3
10
12 30 37 88 12 78 89 17 2 12
6
7 7 7 7 7 7
Output
4
1
5
3
1
21


-----Note-----

In the first test case, you can choose $k = 2$ and split the array into subsegments $(1, 2)$ and $(3, 4)$.

Then the score of such a partition will be equal to $\gcd(a_1 + a_2, a_3 + a_4) = \gcd(2 + 2, 1 + 3) = \gcd(4, 4) = 4$.

In the fourth test case, you can choose $k = 3$ and split the array into subsegments $(1, 2), (3, 5), (6, 6)$.

The split score is $\gcd(1 + 2, 1 + 1 + 1, 3) = 3$.

Source: codeforces | Difficulty: EASY
Tags: Number theory

Complete search

Mathematics

Greedy algorithms


Solutions:
from itertools import accumulate
from math import gcd

def solution():
	n = int(input())
	nums = [int(num) for num in input().split()]
	a = list(accumulate(nums))
	best = 1
	for num in reversed(a[:n - 1]):
		best = max(best, gcd(a[-1], num))
	print(best)

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


import math

def program():
	n = int(input())
	a = [int(x) for x in input().split()]
	s = 0
	total_sum = sum(a)
	gcd_list = []
	for i in range(0, n - 1):
		s += a[i]
		gcd_list.append(math.gcd(s, total_sum - s))
	return max(gcd_list)
t = int(input())
answers = []
for i in range(0, t):
	answers.append(program())
for i in answers:
	print(i)


import math
for k in [*open(0)][2::2]:
	(*a, k) = map(int, k.split())
	k += sum(a)
	m = r = 0
	for x in a:
		r += x
		m = max(m, math.gcd(k, r))
	print(m)


import math

def main():
	_i = int(input())
	for _ in range(_i):
		n = int(input().strip('\r\n'))
		a = [int(x) for x in input().strip('\r\n').split()]
		s1 = a[0]
		s2 = sum(a) - a[0]
		res = math.gcd(s1, s2)
		for x in a[1:-1]:
			s1 += x
			s2 -= x
			res = max(res, math.gcd(s1, s2))
		print(res)
main()


import sys
import threading
from math import *
from bisect import *
from collections import *
from heapq import *
from functools import *

def gl():
	return list(map(int, input().split()))

def gi():
	return int(input())

def gc():
	return input()
mod = int(pow(10, 9)) + 7

def solution():
	n = gi()
	arr = gl()
	left = 0
	right = sum(arr)
	ans = 1
	for i in range(n - 1):
		left += arr[i]
		right -= arr[i]
		ans = max(ans, gcd(left, right))
	return print(ans)

def main():
	t = gi()
	for _ in range(t):
		solution()
threading.stack_size(1 << 27)
sys.setrecursionlimit(1 << 30)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


import math
T = int(input())
for t in range(0, T):
	maxi = 1
	n = int(input())
	a = list(map(int, input().split(' ')))
	summ = sum(a)
	var = 0
	for i in range(0, n - 1):
		var = var + a[i]
		x = math.gcd(var, summ - var)
		if x > maxi:
			maxi = x
	print(maxi)


from math import gcd

def f(n, L):
	ans = -float('inf')
	total = sum(L)
	sum1 = 0
	ans = 0
	for i in range(len(L)):
		sum1 += L[i]
		total -= L[i]
		if sum1 != 0 and total != 0:
			t = gcd(total, sum1)
			if t > ans:
				ans = t
	return ans
t = int(input())
for i in range(t):
	x = int(input())
	L = [int(d) for d in input().split()]
	print(f(x, L))


from math import *
for i in [*open(0)][2::2]:
	i = list(map(int, i.split()))
	s = sum(i)
	g = 0
	t = 0
	for j in i[:-1]:
		t += j
		g = max(g, gcd(t, s - t))
	print(g)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	S = sum(L)
	L1 = []
	Sum = 0
	for i in range(n - 1):
		Sum += L[i]
		L1.append(gcd(Sum, S - Sum))
	print(max(L1))


from math import gcd

def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	s = sum(a)
	pre = 0
	ans = 0
	for i in range(0, n - 1):
		pre += a[i]
		ans = max(ans, gcd(pre, s - pre))
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from math import gcd

def main():
	for __ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		s = sum(l)
		(su, mx) = (0, -1)
		for i in range(n - 1):
			su += l[i]
			mx = max(mx, gcd(su, s - su))
		print(mx)
main()


import sys
from math import *
from collections import defaultdict, deque
input = sys.stdin.readline
mod = 10 ** 9 + 7
INF = 1061109567
N = int(2 * 10 ** 5 + 5)
LINF = 4557430888798830399

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	sum1 = sum(a)
	sum2 = 0
	ans = 1
	for i in range(n - 1):
		sum2 += a[i]
		ans = max(ans, gcd(sum2, sum1 - sum2))
	print(ans)
T = int(input())
for t in range(T):
	solve()


from math import *
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	s = sum(a)
	m = 1
	c = 0
	for i in range(n - 1):
		c += a[i]
		x = s - c
		z = gcd(c, x)
		if z > m:
			m = z
	print(m)


from math import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	ans = 1
	w = 0
	for i in a[:n - 1]:
		w += i
		ans = max(ans, gcd(w, s - w))
	print(ans)


from math import gcd

def main():
	t = int(input())
	for i in range(0, t):
		n = int(input())
		a = [int(x) for x in input().split(' ')]
		max_gcd = 1
		left_sum = 0
		right_sum = sum(a)
		counter = 0
		for el in a:
			if counter == n - 1:
				break
			counter += 1
			left_sum = left_sum + el
			right_sum = right_sum - el
			temp = gcd(left_sum, right_sum)
			if temp > max_gcd:
				max_gcd = temp
		print(max_gcd)
main()


def main():
	import math
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		for i in range(1, n):
			a[i] += a[i - 1]
		ans = 1
		for i in range(n - 1):
			ans = max(ans, math.gcd(a[n - 1], a[i]))
		print(ans)
main()


import math
t = int(input())
for _ in range(t):
	input()
	x = list(map(int, input().split()))
	sm = sum(x)
	cnt = 0
	mx = 1
	for a in x[:-1]:
		cnt += a
		mx = max(math.gcd(cnt, sm), mx)
	print(mx)


import math
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	sum = []
	Total = 0
	for i in arr:
		Total += i
		sum.append(Total)
	ans = math.gcd(sum[0], Total - sum[0])
	for i in range(1, n - 1):
		if ans < math.gcd(sum[i], Total - sum[i]):
			ans = math.gcd(sum[i], Total - sum[i])
	print(ans)


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


import math
t = int(input())
for i in range(t):
	n = int(input())
	numbers = [int(num) for num in input().split(' ', n - 1)]
	sum1 = sum(numbers)
	sum2 = 0
	ans = []
	for j in range(n - 1):
		sum2 += numbers[j]
		ans.append(math.gcd(sum2, sum1 - sum2))
	print(max(ans))


from math import gcd
t = int(input())
for p in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sum = []
	cnt = 0
	for i in range(n):
		cnt += a[i]
		sum.append(cnt)
	maxim = 0
	for i in range(n - 1):
		x = gcd(sum[-1] - sum[i], sum[i])
		if x > maxim:
			maxim = x
	print(maxim)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	s = sum(nums)
	res = 1
	cur = 0
	for i in range(n - 1):
		cur += nums[i]
		res = max(res, gcd(cur, s - cur))
	print(res)


import math
t = int(input())
A = []
for i in range(t):
	n = int(input())
	a = [int(p) for p in input().split()]
	A.append(a)
for i in range(t):
	arr = A[i]
	tot = sum(arr)
	ans = 0
	kiri = 0
	for j in range(len(arr) - 1):
		kiri += arr[j]
		ans = max(ans, math.gcd(kiri, tot - kiri))
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sumo = sum(a)
	temp = 0
	ans = []
	for i in range(n - 1):
		temp += a[i]
		ans.append(math.gcd(temp, sumo - temp))
	print(max(ans))


import math
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	sem = sum(arr)
	k = 0
	ans = 0
	for i in range(n - 1):
		k = k + arr[i]
		ans = max(ans, math.gcd(k, sem - k))
	print(ans)
	t = t - 1


import math
import sys
t = int(input())
for i in range(t):
	n = int(sys.stdin.readline())
	lst = list(map(int, sys.stdin.readline().split()))
	s = sum(lst)
	cur = 0
	ans = 1
	for j in lst[:n - 1]:
		cur += j
		left = s - cur
		ans = max(ans, math.gcd(cur, left))
	print(ans)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from collections import Counter
from bisect import bisect_left as bl, bisect_right as br
import heapq
from itertools import permutations
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007
test = int(input())
for _ in range(test):
	n = inp()
	a = seq()
	add = 0
	ans = 0
	s = sum(a)
	for i in range(len(a) - 1):
		add += a[i]
		s -= a[i]
		ans = max(ans, gcd(s, add))
	print(ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	S = sum(a)
	L = 0
	best = 1
	for x in a[:-1]:
		S -= x
		L += x
		best = max(best, math.gcd(S, L))
	print(best)


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	arr = inlt()
	sumer = sum(arr)
	ans = 0
	ans2 = sumer
	maxer = 1
	for i in arr:
		ans += i
		ans2 -= i
		if ans and ans2:
			maxer = max(maxer, math.gcd(ans, ans2))
	print(maxer)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	biggest_gcd = 0
	l = a[0]
	r = sum(a[1:])
	p = 1
	while r != 0:
		gcd = math.gcd(l, r)
		if gcd > biggest_gcd:
			biggest_gcd = gcd
		l += a[p]
		r -= a[p]
		p += 1
	print(biggest_gcd)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n = inp()
	l = li()
	l1 = []
	m = 0
	s = 0
	for i in l:
		s += i
		l1.append(s)
	for i in range(len(l1) - 1):
		m = max(gcd(l1[-1], l1[i]), m)
	print(m)


import math
for ii in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	fan = 0
	j = 0
	for i in range(n - 1):
		j += a[i]
		fan = max(fan, math.gcd(j, s - j))
	print(fan)


from math import gcd as g
I = input
for i in range(int(I())):
	n = int(I())
	x = list(map(int, I().split()))
	Sum = sum(x)
	(a, b) = (1, 0)
	for i in range(n - 1):
		b += x[i]
		Sum -= x[i]
		a = max(a, g(Sum, b))
	print(a)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	summ = sum(arr)
	maxgcd = 0
	temp = 0
	for i in arr:
		summ -= i
		temp += i
		if summ == 0:
			break
		maxgcd = max(maxgcd, gcd(temp, summ))
	print(maxgcd)


import math
for _ in range(int(input())):
	a = int(input())
	li = list(map(int, input().split()))
	su = sum(li)
	an = 1
	ans = 0
	for i in range(a - 1):
		ans += li[i]
		an = max(an, math.gcd(ans, su - ans))
	print(an)


from math import gcd

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	ans = 0
	sum1 = 0
	for i in range(n - 1):
		sum1 += a[i]
		ans = max(ans, gcd(sum1, s - sum1))
	print(ans)
for _ in range(int(input())):
	solve()


import sys, io, os, math
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n,) = I()
	nums = I()
	sumr = sum(nums)
	suml = 0
	res = 0
	for x in nums[:-1]:
		sumr -= x
		suml += x
		res = max(math.gcd(sumr, suml), res)
	print(res)


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	s = sum(b)
	pre = 0
	after = s
	res = 1
	for i in range(n - 1):
		pre += b[i]
		after -= b[i]
		res = max(res, gcd(pre, after))
	print(res)


import math
iter = int(input())
for _ in range(iter):
	n = int(input())
	a = list(map(int, input().split(' ')))
	s = sum(a)
	pre = 0
	ans = 1
	for i in range(n - 1):
		pre += a[i]
		ans = max(ans, math.gcd(pre, s - pre))
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	sm = sum(x)
	mx_gcd = 1
	p = 0
	for i in x[0:n - 1]:
		p += i
		sm -= i
		gcd = math.gcd(p, sm)
		mx_gcd = max(mx_gcd, gcd)
	print(mx_gcd)


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


import sys
from os import path
import math
gcd = math.gcd
FILE = False
if FILE:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def get_int():
	return int(sys.stdin.readline())

def get_string():
	return sys.stdin.readline().strip()

def find_gcd_partitions(array):
	array_length = len(array)
	left = 0
	sum = 0
	max_gcd = 1
	for n in array:
		sum += n
	for n in array[:-1]:
		left += n
		sum -= n
		b = gcd(left, sum)
		if gcd(left, sum) > max_gcd:
			max_gcd = b
	return max_gcd
num_tests = get_int()
for i in range(num_tests):
	length = get_int()
	array = [int(x) for x in get_string().split(' ')]
	num_max_gcd_partitions = find_gcd_partitions(array)
	sys.stdout.write(str(num_max_gcd_partitions))
	sys.stdout.write('\n')


import math
for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	sume = sum(b)
	m = 0
	ans = 1
	for i in range(a - 1):
		m += b[i]
		ans = max(ans, math.gcd(sume, sume - m))
	print(ans)


from math import gcd
n = int(input())
for j in range(n):
	t = int(input())
	a = list(map(int, input().split()))
	ans = 0
	g = 0
	s = sum(a)
	for i in a[:-1]:
		g += i
		k = gcd(s - g, g)
		if k > ans:
			ans = k
	print(ans)


from sys import stdin, stdout
from math import gcd
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	ml = []
	s = 0
	for i in range(n):
		s += nums[i]
		ml.append(s)
	k = 1
	for j in range(n - 1):
		k = max(gcd(ml[-1], ml[j]), k)
	print(k)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	total = sum(a)
	pre = [0]
	for i in a:
		pre.append(pre[-1] + i)
	ans = 1
	from math import gcd
	for i in range(n - 1):
		x = pre[i + 1]
		y = total - x
		ans = max(ans, gcd(x, y))
	print(ans)


from itertools import *

def check(arr):
	n = len(arr)
	if arr[0] == start and arr[1] == end:
		for i in range(1, n - 1):
			if arr[i] % (i + 1) != 0:
				return 0
		return 1
	else:
		return 0

def func(n):
	lst = []
	for i in range(1, n + 1):
		lst.append(i)
	perm = permutations(lst)
	for i in perm:
		if check(i) == 1:
			print(i)
from math import gcd
t = int(input())
mod = 1000000007
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	total = sum(arr)
	res = 1
	curr = 0
	for i in range(n - 1):
		curr += arr[i]
		last = total - curr
		res = max(res, gcd(curr, last))
	print(res)


import math
for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	(sum1, sum2) = (sum(num), 0)
	ans = 0
	for i in range(n):
		sum1 -= num[i]
		sum2 += num[i]
		if sum1 != 0 and sum2 != 0:
			ans = max(ans, math.gcd(sum1, sum2))
	print(ans)


from math import gcd

def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	if 'codeforces' == 28226329:
		print('Tanmay')
	a = A()
	s = sum(a)
	ans = gcd(a[-1], s - a[-1])
	c = 0
	for i in range(n - 1):
		c += a[i]
		ans = max(ans, gcd(c, s - c))
	print(ans)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	pref = [0]
	for i in arr:
		pref.append(pref[-1] + i)
	del pref[0]
	to = sum(arr)
	idx = 0
	ans = 0
	for i in pref:
		if i < to:
			ans = max(ans, gcd(i, to - i))
	print(ans)


import math
n = int(input())
for _ in range(n):
	x = int(input())
	l = [int(i) for i in input().split()]
	s = sum(l)
	p = 0
	m = 0
	for i in range(x - 1):
		p += l[i]
		s -= l[i]
		m = max(m, math.gcd(p, s))
	print(m)


import math

def solve():
	n = int(input())
	ai = list(map(int, input().split()))
	r = sum(ai)
	l = 0
	ans = 0
	for i in range(n - 1):
		l += ai[i]
		r -= ai[i]
		ans = max(ans, math.gcd(l, r))
	print(ans)
t = int(input())
for _ in range(t):
	solve()


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


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	for v in range(len(a)):
		a[v] = int(a[v])
	max = 0
	a.append(0)
	b = a[0]
	c = sum(a) - b
	for j in range(1, n):
		if math.gcd(b, c) > max:
			max = math.gcd(b, c)
		b += a[j]
		c -= a[j]
	print(max)


import math
t = int(input())
while t > 0:
	n = int(input())
	tab = list(map(int, input().split()))
	s1 = sum(tab)
	s2 = 0
	m = 1
	for i in range(n - 1):
		s2 += tab[i]
		s1 -= tab[i]
		m = max(m, math.gcd(s1, s2))
	print(m)
	t -= 1


import math

def solve():
	n = int(input())
	v = list(map(int, input().split()))
	pre = [0] * n
	rev = [0] * n
	pre[0] = v[0]
	for i in range(1, n):
		pre[i] = pre[i - 1] + v[i]
	rev[n - 1] = v[n - 1]
	for i in range(n - 2, -1, -1):
		rev[i] = rev[i + 1] + v[i]
	ans = 0
	for i in range(n - 1):
		ans = max(ans, math.gcd(pre[i], rev[i + 1]))
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from math import gcd
t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	for i in range(n):
		s += a[i]
	ans = 0
	pref = 0
	for i in range(n - 1):
		pref += a[i]
		ans = max(ans, gcd(pref, s - pref))
	print(ans)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	s = sum(a)
	ans = z = 0
	for i in a[:-1]:
		z += i
		ans = max(ans, gcd(z, s - z))
	print(ans)


import math
T = int(input(''))
for i in range(T):
	n = int(input())
	str1 = input()
	l1 = [int(c) for c in str1.split()]
	leftSum = 0
	rightSum = sum(l1)
	maxGCD = 1
	for j in range(len(l1) - 1):
		leftSum += l1[j]
		rightSum -= l1[j]
		newGCD = math.gcd(leftSum, rightSum)
		if newGCD > maxGCD:
			maxGCD = newGCD
	print(maxGCD)


import sys
if sys.platform == 'ios':
	import clipboard
	a = clipboard.get()
	a = a.split('\n')
	text = '\n'.join(a)
	with open('input_file.txt', 'w') as f:
		f.write(text)
	sys.stdin = open('input_file.txt')
sys.setrecursionlimit(4100000)
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().strip()
from math import gcd
t = int(input())
for _ in range(t):
	N = ni()
	A = list(map(int, input().split()))
	for i in range(1, N):
		A[i] += A[i - 1]
	ans = 0
	for i in range(N - 1):
		x = gcd(A[i], A[-1] - A[i])
		ans = max(x, ans)
	print(ans)


from math import gcd
test_case = int(input())
for test in range(test_case):
	n = int(input())
	A = list(map(int, input().split()))
	S = sum(A)
	P = [0] * n
	P[0] = A[0]
	for i in range(1, n):
		P[i] = P[i - 1] + A[i]
	ans = 0
	for i in range(n - 1):
		d = gcd(P[i], S)
		ans = max(ans, d)
	print(ans)


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	ans = []
	pre = [0] * (n + 1)
	for j in range(1, n + 1):
		pre[j] = pre[j - 1] + a[j - 1]
	pre.remove(0)
	pre.pop(n - 1)
	b = list(map(lambda x: s - x, pre))
	for i in range(n - 1):
		ans.append(math.gcd(pre[i], b[i]))
	print(max(ans))


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


import math
for __ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	acc = 0
	ans = 0
	for i in range(n - 1):
		acc += a[i]
		ans = max(ans, math.gcd(acc, s - acc))
	print(ans)


import math

def ans(arr):
	prf_sum = [arr[0]]
	for i in range(1, len(arr)):
		prf_sum.append(prf_sum[-1] + arr[i])
	max_found = 0
	for i in range(0, len(arr) - 1):
		tmp = math.gcd(prf_sum[i], prf_sum[-1] - prf_sum[i])
		max_found = max(max_found, tmp)
	return max_found
test_cases = int(input())
while test_cases != 0:
	d = input()
	d2 = list(map(int, input().split()))
	print(ans(d2))
	test_cases -= 1


from typing import List
from bisect import *
from collections import *
from functools import *
from itertools import *
from math import *
from queue import PriorityQueue
INF = 2 ** 64 - 1
MOD = 10 ** 9 + 7
mi = lambda : map(int, input().split())
li = lambda : list(mi())

def isPrime(n):
	if n == 1:
		return False
	m = int(sqrt(n))
	for i in range(2, m + 1):
		if n % i == 0:
			return False
	return True

def main(n, nums):
	s = sum(nums)
	ans = 1
	pre = 0
	for i in range(0, n - 1):
		pre += nums[i]
		ans = max(ans, gcd(pre, s - pre))
	print(ans)
	return
caseNum = int(input())
for i in range(0, caseNum):
	n = int(input())
	nums = li()
	main(n, nums)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	sum = 0
	for j in range(n):
		sum += a[j]
	q = 0
	w = 1
	for k in range(n - 1):
		sum -= a[k]
		q += a[k]
		w = max(w, math.gcd(sum, q))
	print(w)


from math import gcd
from functools import reduce

def lstStrRd():
	return list(input())

def intRd():
	return int(input())

def lstRd():
	return list(map(int, input().split()))
for _ in range(intRd()):
	n = intRd()
	l = lstRd()
	z = sum(l)
	c = 0
	ll = [1]
	for i in range(n - 1):
		c += l[i]
		ll.append(gcd(c, z - c))
	print(max(ll))


import math
t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	temp = sum(list1)
	sum1 = temp
	max1 = 1
	div = 0
	for i in range(n - 1, 0, -1):
		div += list1[i]
		sum1 = sum1 - list1[i]
		if math.gcd(sum1, div) > max1:
			max1 = math.gcd(sum1, div)
	print(max1)


import math
t = int(input())
n_arr = []
a_arr = []
for num in range(t):
	n_arr.append(int(input()))
	a_arr.append([int(val) for val in input().split()])
for arr in a_arr:
	left = 0
	right = sum(arr)
	gmax = 0
	for i in range(len(arr) - 1):
		left += arr[i]
		right -= arr[i]
		g = math.gcd(left, right)
		gmax = max(g, gmax)
	print(gmax)


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


import math
for q in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))[:a]
	new = 0
	sum_l = sum(l)
	max_l = 0
	for i in range(a):
		sum_l -= l[i]
		new += l[i]
		if sum_l != 0:
			max_l = max(max_l, math.gcd(sum_l, new))
	print(max_l)


import math
t = int(input())
for i in range(t):
	foo = 1
	n = int(input())
	arr = [n]
	bar = str(input())
	arr = bar.split()
	for j in range(n):
		arr[j] = int(arr[j])
	cum_sum = [arr[0]]
	for j in range(1, n):
		cum_sum.append(cum_sum[j - 1] + arr[j])
	sum = cum_sum[-1]
	for j in range(n - 1):
		a = math.gcd(sum, cum_sum[j])
		if a != 1:
			foo = max(a, foo)
	print(foo)


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


import math
t = int(input())
for k in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	x = sum(c)
	y = 0
	ans = 1
	for i in c[:-1]:
		x -= i
		y += i
		ans = max(ans, math.gcd(x, y))
	print(ans)


import math
t = int(input())
output = []
for i in range(2 * t):
	lst = list(map(int, input().split()))
	if i & 1 == 0:
		n = lst[0]
	else:
		sum_lst = [lst[0]]
		for j in range(1, n):
			sum_lst.append(sum_lst[j - 1] + lst[j])
		gcdList = []
		for j in range(n - 1):
			gcdList.append(math.gcd(sum_lst[n - 1], sum_lst[j]))
		maxi = gcdList[0]
		j = 0
		while j < n - 1:
			if gcdList[j] > maxi:
				maxi = gcdList[j]
				j += 1
			else:
				j += 1
		output.append(maxi)
for i in range(t):
	print(output[i])


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	list1 = []
	x = arr[0]
	list1 = [x]
	max_gcd = 0
	s = 0
	for i in range(1, n):
		list1.append(arr[i] + list1[i - 1])
	s = list1[n - 1]
	for i in range(0, n - 1):
		max_gcd = max(math.gcd(list1[i], s - list1[i]), max_gcd)
	print(max_gcd)


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(pfs, sfs) = (sum(l[:1]), sum(l[1:]))
	ans = math.gcd(pfs, sfs)
	for i in range(1, n - 1):
		pfs = pfs + l[i]
		sfs = sfs - l[i]
		ans = max(ans, math.gcd(pfs, sfs))
	print(ans)


import math
n = int(input())
for i in range(n):
	length = int(input())
	arr = list(map(int, input().split()))
	lol = []
	esum = 0
	for p in range(length):
		esum += arr[p]
		lol.append(esum)
	maxsum = lol[length - 1]
	ans = 1
	for j in range(length - 1):
		ans = max(ans, math.gcd(lol[j], maxsum - lol[j]))
	print(ans)


import math
import copy
t = int(input())
for i in range(t):
	n = int(input())
	z = list(map(int, input().split()))
	b = z.copy()
	d = z.copy()
	for i in range(1, n):
		b[i] = b[i - 1] + b[i]
	for i in range(n - 2, -1, -1):
		d[i] = d[i + 1] + d[i]
	ans = [1]
	for i in range(1, n):
		ans.append(math.gcd(b[i - 1], d[i]))
	print(max(ans))