题目描述

给你一个由n个非负整数组成的数组a。保证a是从小到大排序的。

对于每个操作，我们生成一个新数组$b_i=a_{i+1}-a_i$，1≤i<n。然后我们把b从小到大排序，用b替换a，并把n减少1。

在进行了n-1次操作后，n变成了1。你需要输出数组a中唯一的整数（也就是说，你需要输出$a_1$）。

Format

Input

输入由多个测试案例组成。第一行包含一个整数t（$1\leq t \leq10^4$）--测试案例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数n（$2\leq n \leq10^5$）--数组a的长度。

第二行包含n个整数$a_1$,$a_2$,...,$a_n$（$0\leq a_1\leq...\leq a_n\leq5⋅10^5$）--数组a。

保证每个测试案例的n之和不超过$2.5⋅10^5$

Output

对于每个测试案例，在新的一行中输出答案。

Samples

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

样例解释

sort(a)表示将a从小到大排序后得到的数组。

在第一个测试案例中，一开始a=[1,10,100]。第一次操作后，a=sort([10-1,100-10])=[9,90]。第二次操作后，a=sort([90-9])=[81]。

在第二个测试案例中，起初a=[4,8,9,13]。第一次操作后，a=sort([8-4,9-8,13-9])=[1,4,4]。第二次操作后，a=sort([4-1,4-4])=[0,3]。最后一次操作后，a=sort([3-0])=[3]。