You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

给定一个长度为 $n$ 的递增数组 $a_i$。定义其差分数组 $D(a)$ 是一个长度为 $n-1$ 的数组，且 $D(a)=\operatorname{sort}(\{a_{i+1}-a_i\})$。其中 $\operatorname{sort}(S)$ 表示对 $S$ 进行排序之后的序列。

求 $D(D(\dots D(a)))_1$（$n-1$ 个 $D$）。

输入格式

第一行一个正整数 $T$ 表示测试点数目。

每个测试组，第一行一个正整数 $n$。

接下来 $n$ 个正整数表示 $a_1,a_2,\dots,a_n$。

输出格式

对每个测试点，输出一行一个自然数表示答案。

样例

【样例输入】

5
3
1 10 100
4
4 8 9 13
5
0 0 0 8 13
6
2 4 8 16 32 64
7
0 0 0 0 0 0 0

【样例输出】

81
3
1
2
0

数据范围

对所有数据 $1\leq T\leq 20$，$0\leq a_1\leq a_2\leq\dots\leq a_n\leq 10^9$。

$\color{white}{搬题人马没了}$