给你N个非负整数，你可以将这N个整数按两个一组的方式成对划分，当然其中的元素也可以不和其他元素配对划分。现在的问题是，让划分为一对的元素的乘积与未配对的元素相加求和，并且让和最大。比如：考虑这个集合{0,1,2,4,5,3}，如果我们让{0,3}、{2,5}分别成一对，那么得到的和为：1+4+(0*3)+(2*5)=15,当然这不是最大值，如果这样划分{4,5}、{2，3}分别一组，我们得到的和为：(4*5)+(2*3)+1+0=27,此时得到的和为最大了。

第一行输入一个数M代表有M组数据组成：每组数据第一行输入N，代表有N个整数(1<=N<=100)第二行输入这N个整数。(每个整数都小于100)

输出共m行，每行M对应的最大和。