시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 215 150 131 75.287%

문제

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

예를 들어, 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개가 아닐 수도 있다.

출력

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

예제 입력 1

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

예제 출력 1

7
21
2
W3sicHJvYmxlbV9pZCI6IjI2OTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NjlcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YWQ2Y1x1YWMwNCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjNWI0XHViNWE0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjNzIwXHVjOWMwXHVkNTU4XHViYTc0XHVjMTFjIFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWFkZjhcdWI4ZjlcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViYTc0XHVjMTFjLCBcdWFjMDEgXHVhZGY4XHViOGY5XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWMxOVx1YWM4YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMiwgNSwgMSwgMywgMywgN1x1Yzc0MCAoMiwgNSksICgxLCAzLCAzKSwgKDcpXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWIwOThcdWIyMDRcdWJhNzQgXHVhYzAxIFx1YWRmOFx1YjhmOVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc3NCA3XHViODVjIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM1NDRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWI5N2MgXHVkNTY5XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWFkNmNcdWFjMDRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWQ1NjlcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjYzM4XHVhY2UwXHViODVjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWQxYjVcdWNjNDRcdWI4NWMgXHVhZGY4XHViOGY5IDFcdWFjMWNcdWM1ZDAgXHViMTIzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdmYyBcdWM3NzQgXHViNTRjLCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEgJmx0Oz0gVCAmbHQ7PSAxLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsdDs9IE0gJmx0Oz0gMTAsMDAwKSBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMFx1YjI5NCBcdWFkZjggXHVjMjE4XHVjNWY0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWQ1NWMgXHVjOTA0XHVjNWQwIDEwXHVhYzFjXHVjNTI5IFx1YjA5OFx1YjIwNFx1YzViNFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNzQwIFx1YzIxOFx1YWMwMCAxMFx1YWMxY1x1YWMwMCBcdWM1NDRcdWIyZDAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjY5NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVxdWFsIFN1bSBQYXJ0aXRpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBlcXVhbCBzdW0gcGFydGl0aW9uIG9mIGEgc2VxdWVuY2Ugb2YgbnVtYmVycyBpcyBhIGdyb3VwaW5nIG9mIHRoZSBudW1iZXJzIChpbiB0aGUgc2FtZSBvcmRlciBhcyB0aGUgb3JpZ2luYWwgc2VxdWVuY2UpIGluIHN1Y2ggYSB3YXkgdGhhdCBlYWNoIGdyb3VwIGhhcyB0aGUgc2FtZSBzdW0uIEZvciBleGFtcGxlLCB0aGUgc2VxdWVuY2U6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+MiA1IDEgMyAzIDcmbmJzcDs8XC9wcmU+XHJcblxyXG48cD5tYXkgYmUgZ3JvdXBlZCBhczombmJzcDs8XC9wPlxyXG5cclxuPHByZT4oMiA1KSAoMSAzIDMpICg3KSZuYnNwOzxcL3ByZT5cclxuXHJcbjxwPnRvIHlpZWxkIGFuIGVxdWFsIHN1bSBvZiA3LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgcGFydGl0aW9uIHRoYXQgcHV0cyBhbGwgdGhlIG51bWJlcnMgaW4gYSBzaW5nbGUgZ3JvdXAgaXMgYW4gZXF1YWwgc3VtIHBhcnRpdGlvbiB3aXRoIHRoZSBzdW0gZXF1YWwgdG8gdGhlIHN1bSBvZiBhbGwgdGhlIG51bWJlcnMgaW4gdGhlIHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgdGhpcyBwcm9ibGVtLCB5b3Ugd2lsbCB3cml0ZSBhIHByb2dyYW0gdGhhdCB0YWtlcyBhcyBpbnB1dCBhIHNlcXVlbmNlIG9mIHBvc2l0aXZlIGludGVnZXJzIGFuZCByZXR1cm5zIHRoZSBzbWFsbGVzdCBzdW0gZm9yIGFuIGVxdWFsIHN1bSBwYXJ0aXRpb24gb2YgdGhlIHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIFRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggZGF0YSBzZXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciwgZm9sbG93ZWQgYnkgYSBzcGFjZSwgZm9sbG93ZWQgYnkgYSBkZWNpbWFsIGludGVnZXIgTSwgKDEgJmxlOyBNICZsZTsgMTAwMDApLCBnaXZpbmcgdGhlIHRvdGFsIG51bWJlciBvZiBpbnRlZ2VycyBpbiB0aGUgc2VxdWVuY2UuIFRoZSByZW1haW5pbmcgbGluZShzKSBpbiB0aGUgZGF0YXNldCBjb25zaXN0IG9mIHRoZSB2YWx1ZXMsIDEwIHBlciBsaW5lLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBsYXN0IGxpbmUgaW4gdGhlIGRhdGFzZXQgbWF5IGNvbnRhaW4gbGVzcyB0aGFuIDEwIHZhbHVlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgZ2VuZXJhdGUgb25lIGxpbmUgb2Ygb3V0cHV0IHdpdGggdGhlIGZvbGxvd2luZyB2YWx1ZXM6IFRoZSBkYXRhIHNldCBudW1iZXIgYXMgYSBkZWNpbWFsIGludGVnZXIsIGEgc3BhY2UsIGFuZCB0aGUgc21hbGxlc3Qgc3VtIGZvciBhbiBlcXVhbCBzdW0gcGFydGl0aW9uIG9mIHRoZSBzZXF1ZW5jZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=