Yelisey has an array a of n integers.

If a has length strictly greater than 1, then Yelisei can apply an operation called minimum extraction to it: 

  1. First, Yelisei finds the minimal number m in the array. If there are several identical minima, Yelisey can choose any of them. 
  2. Then the selected minimal element is removed from the array. After that, m is subtracted from each remaining element. 



Thus, after each operation, the length of the array is reduced by 1.

For example, if a = [1, 6, -4, -2, -4], then the minimum element in it is a_3 = -4, which means that after this operation the array will be equal to a=[1 {- (-4)}, 6 {- (-4)}, -2 {- (-4)}, -4 {- (-4)}] = [5, 10, 2, 0].

Since Yelisey likes big numbers, he wants the numbers in the array a to be as big as possible.

Formally speaking, he wants to make the minimum of the numbers in array a to be maximal possible (i.e. he want to maximize a minimum). To do this, Yelisey can apply the minimum extraction operation to the array as many times as he wants (possibly, zero). Note that the operation cannot be applied to an array of length 1.

Help him find what maximal value can the minimal element of the array have after applying several (possibly, zero) minimum extraction operations to the array.

Input

The first line contains an integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The next 2t lines contain descriptions of the test cases.

In the description of each test case, the first line contains an integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the original length of the array a. The second line of the description lists n space-separated integers a_i (-10^9 ≤ a_i ≤ 10^9) — elements of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

Print t lines, each of them containing the answer to the corresponding test case. The answer to the test case is a single integer — the maximal possible minimum in a, which can be obtained by several applications of the described operation to it.

Example

Input


8
1
10
2
0 0
3
-1 2 0
4
2 10 1 7
2
2 3
5
3 2 -4 -2 0
2
-1 1
1
-2


Output


10
0
2
5
2
2
2
-2

Note

In the first example test case, the original length of the array n = 1. Therefore minimum extraction cannot be applied to it. Thus, the array remains unchanged and the answer is a_1 = 10.

In the second set of input data, the array will always consist only of zeros.

In the third set, the array will be changing as follows: [\color{blue}{-1}, 2, 0] → [3, \color{blue}{1}] → [\color{blue}{2}]. The minimum elements are highlighted with \color{blue}{blue}. The maximal one is 2.

In the fourth set, the array will be modified as [2, 10, \color{blue}{1}, 7] → [\color{blue}{1}, 9, 6] → [8, \color{blue}{5}] → [\color{blue}{3}]. Similarly, the maximum of the minimum elements is 5.
import java.io.*;
import java.util.*;

public class A {

    public static void print(int[] arr) {
        //for debugging only
        for (int x : arr)
            System.out.print(x + " ");
        System.out.println();
    }

    public static boolean isPrime(long n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        long sqrtN = (long) Math.sqrt(n) + 1;
        for (long i = 6L; i <= sqrtN; i += 6) {
            if (n % (i - 1) == 0 || n % (i + 1) == 0) return false;
        }
        return true;
    }

    public static long gcd(long a, long b) {
        if (a > b)
            a = (a + b) - (b = a);
        if (a == 0L)
            return b;
        return gcd(b % a, a);
    }

    public static ArrayList<Integer> findDiv(int N) {
        //gens all divisors of N
        ArrayList<Integer> ls1 = new ArrayList<Integer>();
        ArrayList<Integer> ls2 = new ArrayList<Integer>();
        for (int i = 1; i <= (int) (Math.sqrt(N) + 0.00000001); i++)
            if (N % i == 0) {
                ls1.add(i);
                ls2.add(N / i);
            }
        Collections.reverse(ls2);
        for (int b : ls2)
            if (b != ls1.get(ls1.size() - 1))
                ls1.add(b);
        return ls1;
    }

    public static void sort(int[] arr) {
        //because Arrays.sort() uses quicksort which is dumb
        //Collections.sort() uses merge sort
        ArrayList<Integer> ls = new ArrayList<Integer>();
        for (int x : arr)
            ls.add(x);
        Collections.sort(ls);

        for (int i = 0; i < arr.length; i++)
            arr[i] = ls.get(i);
    }

    public static long power(long x, long y, long p) {
        //0^0 = 1
        //Modular Exponentiation (Power in Modular Arithmetic)
        // O(logy)
        long res = 1L;
        x = x % p;
        while (y > 0) {
            if ((y & 1) == 1)
                res = (res * x) % p;
            y >>= 1;
            x = (x * x) % p;
        }
        return res;
    }

    public static void main(String hi[]) throws Exception {
        FastScanner scn = new FastScanner();
        //Write from here
        int t=scn.nextInt();
        while(t-->0)
        {
            int n=scn.nextInt();
            int[] arr=scn.nextInts(n);
            sort(arr);
            int max=Integer.MIN_VALUE;
            for (int i = 1; i < arr.length; i++) {
                if(max<arr[0])
                    max=arr[0];
                if(max<arr[i]-arr[i-1])
                {
                    max=arr[i]-arr[i-1];
                }
            }
            if(max==Integer.MIN_VALUE)
                max=arr[0];
            System.out.println(max);
        }
    }

}


class FastScanner {

    //I don't understand how this works lmao
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }

    public int nextInt() {
        //returns Int
        return (int) nextLong();
    }

    public int[] nextInts(int N) {
        //returns array of integers of size N
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }

    public long[] nextLongs(int N) {
        //returns array of Longs of size N
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public long nextLong() {
        //return long
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }

    public double nextDouble() {
        //return double
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }

    public double[] nextDoubles(int N) {
        //return array of doubles
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}
