YJQQQAQ has an array A of length n. He defines a function fl,r,k where l,r,k are positive integers that satisfies l≤r and r×k≤n, and the value of the function equals to p×q×⌊k√⌋ where p equals to the sum value of Al×k,A(l+1)×k,...,Ar×k and q equals to the minimal value of them. YJQQQAQ wants to choose the positive integers l,r,k carefully to maximize the value of the function.
The first line contains an integer T(1≤T≤3)——The number of the test cases. For each test case:
The first line contains an integers n(1≤n≤300,000).
The second line contains n integers describing the given array A, the ith integer is Ai(1≤Ai≤1,000,000). Between each two adjacent integers there is a white space separated.
For each test case, the only line contains the only integer that is the maximum value of the function.
2 3 1