# Difference Array Solution Codeforces

You are given an array aa consisting of nn non-negative integers. It is guaranteed that aa is sorted from small to large.

For each operation, we generate a new array bi=ai+1aibi=ai+1−ai for 1i<n1≤i<n. Then we sort bb from small to large, replace aa with bb, and decrease nn by 11.

After performing n1n−1 operations, nn becomes 11. You need to output the only integer in array aa (that is to say, you need to output a1a1).

## Input Difference Array Solution Codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1t1041≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer nn (2n1052≤n≤105) — the length of the array aa.

The second line contains nn integers a1,a2,,ana1,a2,…,an (0a1an51050≤a1≤…≤an≤5⋅105) — the array aa.

It is guaranteed that the sum of nn over all test cases does not exceed 2.51052.5⋅105, and the sum of anan over all test cases does not exceed 51055⋅105.

### Output Difference Array Solution Codeforces

For each test case, output the answer on a new line.

Example
input

Copy
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

output

Copy
81
3
1
2
0


## Note Difference Array Solution Codeforces

To simplify the notes, let sort(a)sort⁡(a) denote the array you get by sorting aa from small to large.

In the first test case, a=[1,10,100]a=[1,10,100] at first. After the first operation, a=sort([101,10010])=[9,90]a=sort⁡([10−1,100−10])=[9,90]. After the second operation, a=sort()=a=sort⁡([90−9])=.

In the second test case, a=[4,8,9,13]a=[4,8,9,13] at first. After the first operation, a=sort([84,98,139])=[1,4,4]a=sort⁡([8−4,9−8,13−9])=[1,4,4]. After the second operation, a=sort([41,44])=[0,3]a=sort⁡([4−1,4−4])=[0,3]. After the last operation, a=sort()=a=sort⁡([3−0])=.