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).