숙제

계룡대학교의 배 교수는 "문제 해결"이라는 수업을 맡고 있다. 이 수업의 수강생은 수업 바로 전날 나온 숙제를 놓고 서로 토론하기 때문에, 숙제는 하루 안에 끝내야 한다.

배 교수는 게을러서 숙제를 수강생 한 명에게만 알려 주고, 나머지는 수강생끼리 전화로 옮기기를 바란다. 다행히 수강생은 서로의 전화번호를 모두 안다. 하지만 점수에 목을 매는 수강생은 숙제를 전달받아도 곧바로 남에게 알리지 않고, 자기 숙제를 끝낸 뒤에야 전화를 건다.

수강생은 $N$명이고 $s_1, s_2, \dots, s_N$이라고 하자. $s_i$가 숙제를 끝내는 데 걸리는 시간은 $t_i$시간이다. 시간은 다음 규칙대로 흐른다.

• 0시에 배 교수가 $s_1$에게 숙제를 알린다.
• $a$시에 숙제를 전달받은 $s_i$는 $a + t_i$시에 숙제를 끝낸다.
• 숙제를 끝낸 학생은 자신이 끝낸 시각부터 한 시간에 한 명씩 아직 숙제를 모르는 학생에게 전화를 건다. 즉 $a + t_i$시, $a + t_i + 1$시, $a + t_i + 2$시와 같이 이어진다.
• 전화를 받은 학생은 그 시각에 곧바로 숙제를 시작한다.

모든 수강생이 숙제를 끝내는 데 걸리는 가장 짧은 시간을 시간 단위로 구하는 프로그램을 작성하시오.

$N = 3$, $t_1 = 1$, $t_2 = 1$, $t_3 = 3$이고 배 교수가 3시에 $s_1$에게 숙제를 알린 경우를 보자. $s_1$은 4시에 숙제를 끝낸다. $s_1$이 4시에 $s_2$에게 알리면 $s_2$는 5시에 끝내고, 5시에 $s_1$이나 $s_2$가 $s_3$에게 알릴 수 있다. 이때 $s_3$은 8시에 끝내므로 모두 끝내는 데 5시간이 걸린다. 반면 $s_1$이 4시에 $s_3$에게 먼저 알리면 4시간 만에 끝난다.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수강생 수 $N$ ($1 \le N \le 10$)이 주어지고, 둘째 줄에는 $N$개의 정수 $t_1, t_2, \dots, t_N$ ($1 \le t_i \le 10$)이 주어진다. 배 교수는 항상 $s_1$에게 숙제를 가장 먼저 알린다.

출력은 표준 출력으로 한다. 테스트 케이스마다 한 줄씩, 모든 수강생이 숙제를 끝내는 데 걸리는 가장 짧은 시간을 정수로 출력한다.