该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

森林乐团今晚要举办一年一度的 月光音乐会。为了抢到最前排的位置，来自各地的小动物们提前许久就开始陆续排队。

这一次，森林秩序由热心的小熊 噜噜（Lulu） 负责维持。他在入口前摆好了 两条排队通道，并要求所有动物按到达顺序来排队，由他负责分配到队伍 A 或队伍 B 中。

每只小动物都有一个 音乐敏感度，用整数表示。排在同一队伍中、相邻的两只动物会互相聊音乐，但如果敏感度差太多，就会出现分歧。

如果相邻两只动物敏感度为 $x$ 和 $y$，冲突值为：$|x - y|$

噜噜想让音乐会的气氛保持和谐，因此希望 两条队伍中所有相邻动物之间的冲突值总和最小。

现在森林动物按顺序陆续到来，你知道每一个动物的音乐敏感度。你需要帮助噜噜计算：

按顺序将它们分配到两条队伍中的所有可行方案里，最小总冲突值是多少？

你需要回答 $t$ 组独立的问题。

输入格式

第一行一个整数 $t$，表示询问次数。 每组询问包含:

• 第一行一个整数 $n$，表示动物数量；
• 第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，按到达顺序给出每只动物的音乐敏感度。

输出格式

每组输出一个整数，表示最小的总冲突值。

样例输入 #1

2
2
2 4
3
2 4 6

样例输出 #1

0
2

样例解释

• 第一组：两只动物分别站在不同队伍中 $\rightarrow$ 相邻关系为零 $\rightarrow$ 冲突 $0$
• 第二组：最佳安排是：
  • 队伍 $A$：$2, 4$
  • 队伍 $B$：$6$
    $\rightarrow$ 总冲突 = $|4 - 2| = 2$

样例输入 #2

1
9
3 5 6 3 1 7 8 1 8

样例输出 #2

5

样例解释

噜噜最终安排成：

• 队伍 $A$：$3, 3, 1, 1$
• 队伍 $B$：$5, 6, 7, 8, 8$ 所有相邻记录冲突和为 5，是所有分法中最和谐的。

数据范围

其它约束：
$1 \le t \le 10$，$1 \le a_i \le 10^9$