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