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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.System.*;
import static java.util.Arrays.sort;
import static java.util.Collections.replaceAll;
import static java.util.Collections.reverseOrder;

public class C {
    public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE") == null;
    // public static final boolean LOCAL = System.getProperty("LOCAL")!=null;
    public static final String ANSI_RED = "\u001B[31m";
    public static final String ANSI_RESET = "\u001B[0m";
    static final int M = (int) 1e9 + 7;
    static final long MM = (long) M * M;
    static final int MAX = Integer.MAX_VALUE;
    static final int MIN = Integer.MIN_VALUE;
    static final int SIZE = (int) 1e9 * 2;
    static ArrayList<Integer> primes = new ArrayList<>();
    //static Scanner sc = new Scanner(System.in);
    static FastReader sc = new FastReader();
    static long startTime;
    static long endTime;
    static boolean[] prime;
    static int[] visited;
    static ArrayList<ArrayList<Integer>> graph;
    static ArrayList<Integer> dfs;
    static boolean isCyclic = false;

    public static int swap(int... args) {
        return args[0];
    }

    public static void main(String[] args) throws IOException {
        do {
            startTime = currentTimeMillis();
            //setOut(new PrintStream("output"));
            //setIn(new FileInputStream("input"));
            lcms[0] = 2;
            for (int k = 1 ; k < lcms.length; k++) {
                lcms[k] = lcm(lcms[k-1],k+2);
            }

            int T = sc.nextInt();while (T-- != 0)
            {
                solve();

            }
            endTime = currentTimeMillis();
            long duration = endTime - startTime;
            //out.println(duration);
            if (false) {
                out.println(max(3, 2));
                Integer[] ARRAY = new Integer[2];
                ArrayList<Integer> LIST = new ArrayList<>();
                LIST.add(2);
                // sort(LIST, reverseOrder());
                LIST.sort(reverseOrder());
                sort(ARRAY, reverseOrder());
                out.println(LIST + " " + Arrays.toString(ARRAY));
            }
        } while (LOCAL);
    }
   static long[] lcms = new long[100000];
    public static void solve(){
/////////////////////////////////////////////////////////////////////
        int n =sc.nextInt();
    Integer [] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i]=sc.nextInt();
        }
        Arrays.sort(arr);
     //   long ans = arr[n-1];
        long sum = arr[0];
        long min = arr[0];
        for (int i = 1; i < n; i++) {
            min = Long.max(min,arr[i]-sum);
            sum+=(arr[i]-sum);


        }
        out.println(min);
///////////////////////////////////////////////////////////////////////

    }
    static void dfs(int src) {
        visited[src] = 1;
        for (Integer integer : graph.get(src)) {
            if (visited[integer] != 1) {
                dfs(integer);
            }
        }
        dfs.add(src);

    }

    static void detectCycle(int src) {
        visited[src] = 2;
        for (Integer integer : graph.get(src)) {
            if (visited[integer] == 0) {
                detectCycle(integer);
            } else if (visited[integer] == 2) {
                isCyclic = true;
                return;
            }

        }
        visited[src] = 1;
    }

    static <Array, Target> int count(Array[] array, Target target) {
        int cn = 0;
        for (Array value : array) {
            if (value.equals(target)) cn++;
        }
        return cn;
    }

    static int count(String string, char target) {
        int cn = 0;
        for (int i = 0; i < string.length(); i++) {
            if (string.charAt(i) == target) cn++;
        }
        return cn;
    }

    static <Array> void revArray(Array[] arr) {
        int n = arr.length;
        for (int i = 0; i < n / 2; i++) {
            Array temp = arr[i];
            arr[i] = arr[n - i - 1];
            arr[n - i - 1] = temp;
        }

    }

    static <Array> void printArray(Array[] arr) {
        int n = arr.length;
        for (Array array : arr) out.print(array + " ");
        out.println();
    }

    static void yes() {
        out.println("YES");
    }

    static void no() {
        out.println("NO");
    }

    public static boolean isPal(String s) {
        StringBuilder stringBuilder = new StringBuilder(s);
        return s.equals(stringBuilder.reverse().toString());
    }

    public static int lowerBound(Integer[] array, int length, int value) {
        int low = -1;
        int hi = length;
        while (low + 1 < hi) {
            int mid = (low + hi) / 2;
            if (array[mid] <= value) {
                low = mid;
            } else {
                hi = mid;
            }
        }
        return low;
    }

    public static int upperBound(Integer[] array, int length, int value) {
        int low = -1;
        int hi = length;
        while (low + 1 < hi) {
            int mid = (low + hi) >> 1;
            if (array[mid] >= value) {
                hi = mid;
            } else low = mid;
        }
        return hi;
    }

    public static int binarySearch(Integer[] arr, int length, int value) {
        int low = 0;
        int hi = length - 1;
        int ans = -1;
        while (low <= hi) {
            int mid = (low + hi) >> 1;
            if (arr[mid] > value) {
                hi = mid - 1;
            } else if (arr[mid] < value) {
                low = mid + 1;
            } else {
                ans = mid;
                break;
            }
        }
        return ans;
    }

    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static long lcm(long  a, long b) {
        return a / gcd(a, b) * b;
    }

    public static int countDivs(int n) {
        int cn = 0;
        int sqr = (int) Math.sqrt(n);
        for (int i = 1; i <= sqr; ++i) {
            if (n % i == 0) {
                ++cn;
            }
        }
        cn *= 2;
        if (sqr * sqr == n) cn--;
        return cn;
    }

    static void prime(int x) {
        //sieve algorithm. nlog(log(n)).
        prime = new boolean[(x + 1)];
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for (int i = 2; i * i <= x; i++)
            if (prime[i])
                for (int j = i * i; j <= x; j += i)
                    prime[j] = false;
    }

    static boolean isEven(long x) {
        return x % 2 == 0;
    }

    static boolean isPrime(long x) {
        boolean flag = true;
        int sqr = (int) Math.sqrt(x);
        if (x < 2) return false;
        for (int i = 2; i <= sqr; i++) {
            if (x % i == 0) {
                flag = false;
                break;
            }
        }
        return flag;
    }

    static long factorial(long x) {
        long total = 1;
        for (int i = 2; i <= x; i++)
            total = (total * i) % M;
        return total;
    }

    static long power(long x, long n) {
        if (n == 0) {
            return 1;
        }
        long pow = power(x, n / 2L);
        if ((n & 1) == 1) {
            return (x * (pow) * (pow));
        }
        return (pow * pow);
    }

    private static <T> String ts(T t) {
        if (t == null) {
            return "null";
        }
        try {
            return ts((Iterable) t);
        } catch (ClassCastException e) {
            if (t instanceof int[]) {
                String s = Arrays.toString((int[]) t);
                return "{" + s.substring(1, s.length() - 1) + "}";
            } else if (t instanceof long[]) {
                String s = Arrays.toString((long[]) t);
                return "{" + s.substring(1, s.length() - 1) + "}";
            } else if (t instanceof char[]) {
                String s = Arrays.toString((char[]) t);
                return "{" + s.substring(1, s.length() - 1) + "}";
            } else if (t instanceof double[]) {
                String s = Arrays.toString((double[]) t);
                return "{" + s.substring(1, s.length() - 1) + "}";
            } else if (t instanceof boolean[]) {
                String s = Arrays.toString((boolean[]) t);
                return "{" + s.substring(1, s.length() - 1) + "}";
            }
            try {
                return ts((Object[]) t);
            } catch (ClassCastException e1) {
                return t.toString();
            }
        }
    }

    private static <T> String ts(T[] arr) {
        StringBuilder ret = new StringBuilder();
        ret.append("{");
        boolean first = true;
        for (T t : arr) {
            if (!first) {
                ret.append(", ");
            }
            first = false;
            ret.append(ts(t));
        }
        ret.append("}");
        return ret.toString();
    }

    private static <T> String ts(Iterable<T> iter) {
        StringBuilder ret = new StringBuilder();
        ret.append("{");
        boolean first = true;
        for (T t : iter) {
            if (!first) {
                ret.append(", ");
            }
            first = false;
            ret.append(ts(t));
        }
        ret.append("}");
        return ret.toString();
    }

    public static void dbg(Object... o) {
        if (LOCAL) {
            System.err.print("Line #" + Thread.currentThread().getStackTrace()[2].getLineNumber() + ": [");
            for (int i = 0; i < o.length; i++) {
                if (i != 0) {
                    System.err.print(", ");
                }
                System.err.print(ts(o[i]));
            }
            System.err.println("]");
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    static class Pair implements Comparable<Pair> {
        private final int key;
        private final int value;

        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public int second() {
            return value;
        }

        @Override
        public int compareTo(Pair o) {
            return -Integer.compare(key, o.key);
        }

        @Override
        public String toString() {
            return "Pair{" + "x=" + key + ", y=" + value + '}';
        }
    }

}