版权声明

本题版权归 Long Long OJ 所有。

题目描述

众所周知，小 naive 有 $n$ 个瓶子，它们在桌子上排成一排。第 $i$ 个瓶子的颜色为 $c_i$。每个瓶子都有灵性，每次操作可以选择两个相邻的瓶子，消耗它们颜色的数值乘积的代价，将其中一个瓶子的颜色变成另一个瓶子的颜色。

现在小 naive 要让所有瓶子的颜色都一样，操作次数不限，但要使得操作的总代价最小。

输入格式

本题有多组数据。

第一行，一个正整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $n$，表示瓶子的个数。

第二行共 $n$ 个整数，第 $i$ 个整数为第 $i$ 个瓶子的颜色 $c_i$。

输出格式

对于每组数据，输出一行一个整数，表示最小的总代价。

样例

1
4
7 4 6 10

92

提示

样例解释：

初始状态为 $\{7, 4, 6, 10\}$：

• 第一次操作：$\{7, 4, 6, 10\} \to \{4, 4, 6, 10\}$，代价为 $7 \times 4 = 28$。
• 第二次操作：$\{4, 4, 6, 10\} \to \{4, 4, 4, 10\}$，代价为 $4 \times 6 = 24$。
• 第三次操作：$\{4, 4, 4, 10\} \to \{4, 4, 4, 4\}$，代价为 $4 \times 10 = 40$。

总代价为 $28 + 24 + 40 = 92$。

$1 \leq T \leq 10$，$1 \leq n \leq 300$，$1 \leq c_i \leq 2 \times 10^5$。