YJQQQAQ has an array $A$ of length $n$. He defines a function $f_{l,r,k}$ where $l,r,k$ are positive integers that satisfies $l\leq r$ and $r\times k\leq n$, and the value of the function equals to $p\times q\times\lfloor\sqrt{k}\rfloor$ where $p$ equals to the sum value of $A_{l\times k},A_{\left(l+1\right)\times k},...,A_{r\times 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\left(1\leq T\leq 3\right)$——The number of the test cases. For each test case: The first line contains an integers $n\left(1\leq n\leq300,000\right)$. The second line contains $n$ integers describing the given array $A$, the $i$th integer is $A_i\left(1\leq A_i\leq1,000,000\right)$. 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.
输入样例
1
3
2 3 1
输出样例
10
提示
When and only when $l=1,r=2,k=1$, the value of the function is the maximum.