Sequence I
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

You are given a sequence of length N. Each time you can delete two adjacent numbers, and insert the absolute value of their difference in the corresponding position. What is the mininum number you can get after N-1 operations? (The number you get means the only one integer left after N-1 operations.)

输入描述:

The first line of input contains an integer , denoting the number of test cases.
Each test case contains two lines:
The first line contains one integer , denoting the length of the sequence;
The second line contains N integers , denoting the sequence.

输出描述:

For each test case, print one integer in one line, denoting your answer.
示例1

输入

复制 
5
2
1 1
2
2 3
2
3 2
3
999 1 1
4
80 87 50 54

输出

复制 
0
1
1
997
3