시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 180 125 108 77.698%

문제

어떤 수열이 있을 때, 순서를 유지하면서 적절히 그룹으로 나누면서, 각 그룹에 들어있는 수의 합을 같게 만들 수 있다.

예를 들어, 2, 5, 1, 3, 3, 7은 (2, 5), (1, 3, 3), (7)와 같이 나누면 각 그룹에 들어있는 수의 합이 7로 모두 같아진다.

양의 정수로 이루어진 수열이 주어졌을 때, 이를 합이 같은 구간으로 나누는 방법을 여러가지가 있다. 이 때, 합의 최소값을 구하시오.

참고로 수열을 통채로 그룹 1개에 넣을 수 있다. 그럼 이 때, 수의 합은 수열의 합이 된다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 첫째 줄에 수열의 크기 M이 주어진다. (1 <= M <= 10,000) 그 다음 줄부터는 그 수열에 들어있는 수가 주어지고, 한 줄에 10개씩 나누어서 주어진다. 따라서 마지막 줄은 수가 10개가 아닐 수도 있다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 문제에서 설명한 가장 작은 합을 출력한다.

예제 입력

3
6
2 5 1 3 3 7
6
1 2 3 4 5 6
20
1 1 2 1 1 2 1 1 2 1
1 2 1 1 2 1 1 2 1 1

예제 출력

7
21
2

힌트