408503: GYM103158 H Annoying posts

Compo was going through his feed on FB site consisting of Khaled Hamed's posts that decrease people's IQ mixed with different posts that increase the IQ. Sick of this, Compo devised a strategy.

He will open FB at every $$$X-th$$$ minute and read all the posts he hadn't read. It's well known that Compo receives exactly one post per minute. where the $$$i-th$$$ post adds $$$A_i$$$ points to his IQ.

Considering that Compo doesn't need any time to read the posts Choose an $$$X$$$ that will maximize the minimum IQ of a single batch of posts that combo reads at once.

The first line of the input contains one integer $$$T$$$ $$$(1 \leq T \leq 10)$$$ the number of test cases.

The first line of each test case contains a number $$$N$$$ $$$(1 \leq N \leq 10^5)$$$.

The second line of each test case contains an integer array $$$A_i$$$ $$$(-10^5 \leq A_i \leq 10^5)$$$.

Print the maximum minimum IQ of a single batch.

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

-10
10