题目描述

Sasha 有 $n$ 个数字组成的序列 $a$ ， 请你对其进行染色。

你要对序列中的每一个元素都进行染色。你可以使用你想用的任意多种颜色，序列中的每个元素要确切的被染上一种颜色，对于每一种颜色至少保证有一个元素被染成该色。

一种颜色的代价是： $\max(S) - \min(S)$, 其中 $S$ 是指染成同一种颜色的元素集合。总代价是所有颜色的代价之和。

例如：假设你有序列 $a = [\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$, 并且你将其中的所有元素染成了如下的两种颜色：元素位置为 $1$, $2$ 和 $5$ 被染成了颜色 $1$; 位置在 $3$ 和 $4$ 的元素被染成颜色 $2$。

• 颜色 $1$ 的代价为 $\max([1, 5, 4]) - \min([1, 5, 4]) = 5 - 1 = 4$;
• 颜色 $2$ 的代价为 $\max([6, 3]) - \min([6, 3]) = 6 - 3 = 3$;
• 总代价为 $7$.

给定序列 $a$, 请你计算可能的最大总代价。

输入

第一行一个整数 $t$ ($1 \leq t \leq 1000$) — 表示测试的组数.

每组的第一行包含一个整数 $n$ ($1 \le n \le 50$) — 表示序列 $a$ 的长度.

第二行包含 $n$ 整数 $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 50$) — 表示序列 $a$.

输出

对于每组测试输出一个可能的最大代价。

样例

6
5
1 5 6 3 4
1
5
4
1 6 3 9
6
1 13 9 3 7 2
4
2 2 2 2
5
4 5 2 2 3

7
0
11
23
0
5

样例解释

对于第一个样例数据，一种可能的染色方式为 $[\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$. 答案就是 $(5 - 1) + (6 - 3) = 7$.

在第二个样例中，仅一种染色方式 $[\color{blue}{5}]$, 答案为 $5 - 5 = 0$.

在第三个样例中，可能的一种染色方式为 $[\color{blue}{1}, \color{red}{6}, \color{red}{3}, \color{blue}{9}]$, 答案为 $(9 - 1) + (6 - 3) = 11$.