K. Two Subarrays
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this problem, subarray is defined as non-empty sequence of consecutive elements of an array.

The strength of an array Z of size K is computed as follows:

Given an array A of size N, find the maximum possible absolute difference between the strengths of two non-intersecting subarrays of A.

Two subarrays intersect if they have common indices.

Input

The first line of the input contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.

Each case contains two lines. The first line contains an integer N (2 ≤ N ≤ 105), the size of the array A.

The second line contains N space-separated integers representing the elements of the array A ( - 109 ≤ Ai ≤ 109).

Output

For each test case, print the maximum possible absolute difference on a single line.

Example
Input
3
4
0 1 2 100
6
-9 1 -3 5 4 2
5
4 3 2 3 4
Output
101
22
5