There are N warehouses. The warehouses are located in a straight line and are indexed from 1 to N. Each warehouse contains some number of sacks.

A thief decides to rob these warehouses. Thief figured out that he can escape the police if and only if he follows both the following 2 constraints:

He will rob only one continuous segment of warehouses.
He will rob same number of sacks from each warehouse.

Thief wants to calculate the maximum number of sacks he can steal without getting caught by the police.

Input Format:

The first line contains an integer T denoting number test cases.

The first line of each test case contains a single integer N denoting number of warehouses.

The second line of each test case contains N space-separated integers :\(a[1],a[2],a[3]...a[n]. a[i]\) denotes number of sacks in \(i_{th}\) warehouse.

Constraints:

\(1 <= T <= 5\)
\(1 <= N <= 10^6\)
\(0 <= A[i] <= 10^{12}\)

Output Format:

Output exactly T lines.

The \(i_{th}\) line should contain a single integer, i.e the answer for \(i_{th}\) testcase(maximum number of sacks thief can steal without getting caught).