有一年暑假，真琴来到了鸟白岛。稻荷很开心，于是她们开始玩一个简单的小游戏。
首先拿出 $n$ 张牌，每张牌有一个编号。现在裁判员苍规定这 $n$ 张牌合法的排列要满足编号为 $i$ 的牌不可以放在位置 $p_i$ 上。
然后稻荷会摆放这些牌，同时这样定义这个序列的 $key$ 值：
记编号为 $i$ 的牌的位置为 $pos_i$。对于所有两张牌的组合(这两张牌编号为 $i$ 和 $j$)，若满足 $j > i$ 且 $pos_j < pos_i$，那么对 $key$ 值产生的贡献就是 $|i-j|\ \times\ |pos_j-pos_i|$，否则贡献为 $0$。
由于这个问题实在是太简单了，真琴每次都能很快的回答上来。为了证明自己的小狐狸稻荷是最强的，苍趁机刁难道：对于所有合法的排列，它们的 $key$ 值之和为多少呢？
这个问题有点困难，真琴不会了。所以希望您能帮她解决。
如果您解决了，她或许会分一个狐不理肉包给你吃哟 ~
第一行一个整数 $T$，描述数据组数。
对于每组数据第一行是一个整数 $n$，表示牌的数量。
接下来一个长度为 $n$ 的整数序列，第 $i$ 个数为 $p_i$。
保证 $T \le 10$ , $1 \le n \le 16$ , $1 \le p_i \le n$。
共 $T$ 行，每行输出一个整数，第 $i$ 行的整数代表示第$i$个数据的答案。
2 2 1 2 3 1 2 3
1 8
样例解释
第一个数据有 "$2$ $1$" 这一个排列符合要求，贡献为 $1 \times 1=1$，所以答案为 $1$。
第二个数据有 "$2$ $3$ $1$", "$3$ $1$ $2$" 这两个排列符合要求，贡献为 $(2-1) \times (3-1) + (3-1) \times (3-2) + (3-1) \times (2-1) + (3-2) \times (3-1) = 8$，所以答案为 $8$。
Comet OJ