Polynomials

题号：NC305934
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

有 $n$ 个多项式，第 $i$ 个多项式次数为 $a_i$ 。
你希望计算它们的乘积，于是设计了以下算法：
- 每次选择两个多项式，假设下标为 $i,j$ ，将它们删除，并加入它们的乘积（次数为 $a_i+a_j$ ）。其中使用朴素算法计算多项式乘法，因此花费代价为 $(a_i+1)(a_j+1)$ 。
直到只剩下一个多项式时算法终止。求最小总代价。
每个测试点中有多组数据。

输入描述:

第一行，一个整数，表示数据组数 。
对于每组数据：
第一行，一个整数 。
第二行， 个整数 。

输出描述:

对于每组数据：
一行，一个整数，表示答案。

示例1

输入

复制

3
3
1 2 3
4
4 3 4 5
9
9 9 8 2 4 4 3 5 3

输出

复制

22
130
1104

备注:

。