같은 합으로 나누기

양의 정수로 이루어진 수열을 순서를 바꾸지 않고 하나 이상의 연속한 구간으로 나누려고 한다. 모든 구간의 원소 합은 서로 같아야 한다.

예를 들어 2, 5, 1, 3, 3, 7은 (2, 5), (1, 3, 3), (7)로 나누면 각 구간의 합이 모두 7이다.

수열 전체를 하나의 구간으로 두는 것도 허용된다. 이때 공통 합은 수열 전체의 합이다. 주어진 수열을 조건에 맞게 나눌 때 가능한 공통 합의 최솟값을 구하시오.

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 50)가 주어진다.

각 테스트 케이스에서는 먼저 수열의 길이 M (1 ≤ M ≤ 10,000)이 한 줄에 주어진다. 이어서 수열의 원소 M개가 주어진다. 입력에서는 한 줄에 최대 10개씩 원소가 나뉘어 주어지므로 마지막 줄에는 10개보다 적은 원소가 있을 수 있다. 각 원소는 10,000 이하의 자연수이다.

각 테스트 케이스마다 조건을 만족하는 공통 구간 합의 최솟값을 한 줄에 하나씩 출력한다.