问题描述
YJQQQAQ有一个长度为$n$的数组$A$。他定义了一个函数$f_{l,r,k}$，其中$l,r,k$是满足$l\leq r$且$r\times k\leq n$的正整数。函数值等于$p\times q\times\lfloor\sqrt{k}\rfloor$，其中$p$是$A_{l\times k},A_{\left(l+1\right)\times k},...,A_{r\times k}$的和值，而$q$是这些数的最小值。YJQQQAQ想要仔细选择$l,r,k$以最大化函数值。
输入描述
有多组测试数据，第一行一个整数$T\left(1\leq T\leq3\right)$，表示测试数据的组数。对于每组测试数据：
第一行，一个整数$n\left(1\leq n\leq300,000\right)$。
第二行，共$n$个整数，其中第$i$个整数是$A_i\left(1\leq A_i\leq1,000,000\right)$，相邻两个整数之间有一个空格隔开。
输出描述
对于每组测试数据，仅一行，一个整数，即最大的函数值。
输入样例
1
3
2 3 1
输出样例
10
Hint
当且仅当$l=1,r=2,k=1$时，函数取得最大值。
