Homework

Professor Bae teaches a class called "Problem Solving" at Gyeryong University. The students discuss the homework that was assigned the day before the class, so every assignment has to be finished within that one day.

Professor Bae is lazy. He announces the homework to exactly one student and expects the students to pass it along by phone. Every student knows every other student's number. Students care only about their own score, so nobody passes the news on right away. A student starts making calls only after finishing the homework.

There are $N$ students, $s_1, s_2, \dots, s_N$, and $s_i$ needs $t_i$ hours to finish an assignment. The clock works like this.

• At hour 0 Professor Bae announces the homework to $s_1$.
• A student $s_i$ who hears about the homework at hour $a$ finishes it at hour $a + t_i$.
• Starting at the hour it finishes, that student calls one student per hour who has not heard yet, so at hours $a + t_i$, $a + t_i + 1$, $a + t_i + 2$, and onward.
• A student who takes a call starts the homework at that same hour.

Write a program that computes the shortest time, in hours, for every student to finish the homework.

Take $N = 3$, $t_1 = 1$, $t_2 = 1$, $t_3 = 3$, with Professor Bae announcing the homework to $s_1$ at 3 o'clock. Then $s_1$ finishes at 4 o'clock. If $s_1$ calls $s_2$ at 4 o'clock, $s_2$ finishes at 5 o'clock, and at 5 o'clock either $s_1$ or $s_2$ can call $s_3$. Then $s_3$ finishes at 8 o'clock, so everyone needs 5 hours. If $s_1$ calls $s_3$ first at 4 o'clock, 4 hours are enough.

Your program reads from standard input. The first line holds the number of test cases $T$ ($1 \le T \le 20$). The first line of each test case holds an integer $N$ ($1 \le N \le 10$), the number of students. The next line holds $N$ integers $t_1, t_2, \dots, t_N$ ($1 \le t_i \le 10$). Professor Bae always announces the homework to $s_1$ first.

Your program writes to standard output. Print exactly one line for each test case. The line holds a single integer, the shortest time in hours for every student to finish the homework.