Chiaki 有一个整数数组 $a_1, a_2, \dots, a_n$。Chiaki 可以将数组中的一个元素 $a_x$ 替换为另一个整数 $y$。设替换后的数组为 $b_1, b_2, \dots, b_n$。Chiaki 想知道 $|a_x - y| + \sum_{k=1}^n k \cdot c_k$ 的最小值，其中 $c_k$ 是 $b_1, b_2, \dots, b_k$ 中不同整数的个数。
输入格式
输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：
第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。
保证所有测试数据中 $n$ 的总和不超过 $10^6$。
输出格式
对于每组测试数据，输出一行一个整数，表示答案。
样例
输入 1
1 4 1 2 3 4
输出 1
22