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.util.*;
import java.io.*;

public class Main {
	static long[]fac=new long[200100];
	static long[] two= new long[200100] ;
	static long mod=((long)1e18)+7;
	static String[]pow=new String[63];
	static int n;
	static int x=0;
	static int[][]perm,b;
	static int[]pe,aa,a;
	public static void main(String[] args) throws IOException, InterruptedException{
		int t=sc.nextInt();
		while(t-->0) {
			int n=sc.nextInt();
			Long[]a=new Long[n];
			for (int i = 0; i < a.length; i++) {
				a[i]=sc.nextLong();
			}
			Arrays.sort(a);
			long ans=a[0];
			for (int i = 1; i < a.length; i++) {
				ans=Math.max(ans, a[i]-a[i-1]);
			}
			pw.println(ans);
		}
		
		pw.close();
	}	
	
	public static long[] Extended(long p, long q) {
	      if (q == 0)
	         return new long[] { p, 1, 0 };

	      long[] vals = Extended(q, p % q);
	      long d = vals[0];
	      long a = vals[2];
	      long b = vals[1] - (p / q) * vals[2];
	      return new long[] { d, a, b };
	   }
	
	static class STree{
		int N;
		long[]arr;
		long[]tree;
		int[]lazy;
		long id;
		public static long operation(long x,long y) {
			return x^y;
		}
		
		public STree(int[]a,long id) {
			this.id=id;
			N=1;
			int n=a.length;
			while(N<n) {
				N*=2;
			}
			arr=new long[N+1];
			Arrays.fill(arr, id);
			for (int i = 1; i <= a.length; i++) {
				arr[i]=a[i-1];
			}
			tree=new long[2*N];
			Arrays.fill(tree, id);
			build(1,N,1);
			lazy=new int[2*N];
		}
		
		public void build(int l,int r,int node) {
			if(l==r) {
				tree[node]=arr[l];
				return;
			}
			int mid=(l+r)/2;
			build(l,mid,node*2);
			build(mid+1,r,node*2+1);
			tree[node]=operation(tree[node*2],tree[node*2+1]);
		}
		
//		public void update(int node,int value) {
//			int i=node+N-1;
//			tree[i]=value;
//			i/=2;
//			while(i>0) {
//				tree[i]=operation(tree[i*2], tree[i*2+1]);
//				i/=2;
//			}
//		}
//		
//		public void updateRange(int l,int r,int v) {
//			updateRange(1, N, l, r, 1,v);
//		}
//		
//		public void updateRange(int s,int e,int l,int r,int node,int v) {
//			if(s>=l&&e<=r) {
//				lazy[node]^=v;
//				tree[node]=propagate(tree[node],lazy[node],e-s+1);
////				lazy[node]=0;
//				return;
//			}
//			if(s>r||e<l)return;
//			int mid=(s+e)/2;
//			lazy[node*2] ^= lazy[node];
//			lazy[node*2+1] ^= lazy[node];
//			tree[node*2] = propagate(tree[node*2], v, (e-s+1)/2);
//			tree[node*2+1] =  propagate(tree[node*2+1], v, (e-s+1)/2);
//			lazy[node] = 0;
//			updateRange(s, mid, l, r, node*2, v);
//			updateRange(mid+1, e, l, r, node*2+1, v);
//			tree[node]=operation(tree[node*2], tree[node*2+1]);
//			return;
//		}
//		
		public long q(int l,int r) {
			return q(1,N,l,r,1);
		}
		
		public long q(int s,int e,int l,int r,int node) {
			if(s>=l&&r>=e) {
				return tree[node];
			}
			if(s>r||e<l)
				return id;
			int mid=(s+e)/2;
			
			return operation(q(s,mid,l,r,node*2), q(mid+1,e,l,r,node*2+1));
		}
//		public static segment propagate(segment x,int v,int length) {
//			int[]bit=x.bit.clone();
//			long sum=x.sum;
//			for (int i = 0; i < bit.length; i++) {
//				if((v&1<<i)!=0) {
//					sum-=(1<<i)*(bit[i]);
//					sum+=(1<<i)*(length-bit[i]);
//					bit[i]=length-bit[i];
//				}
//			}
//			return new segment(sum, bit);
//		}
	}

	public static class segment{
		long sum;
		int[] bit;
		
		public segment (long sum,int[]bit) {
			this.sum=sum;
			this.bit=bit.clone();
		}
		
		@Override
		public String toString() {
			return sum+" "+Arrays.toString(bit);
		}
	}
	
	public static int LIS(int[] a) {

		int n = a.length;
		int[] ser = new int[n];
		int[]ser1=new int[n];
		Arrays.fill(ser1, Integer.MAX_VALUE);
		Arrays.fill(ser, Integer.MAX_VALUE);
		int cur = -1;
		int[]inc=new int[n];
		int[]dec=new int[n];
		for (int i = 0; i < n; i++) {
			int low = 0;
			int high = n - 1;
			int mid = (low + high) / 2;
			while (low <= high) {
				if (ser[mid] < a[i]) {
					low = mid + 1;
				} else {
					high = mid - 1;
				}
				mid = (low + high) / 2;
			}
			inc[i]=high+2;
			cur = Math.max(cur, high + 1);
			ser[high + 1] = Math.min(ser[high + 1], a[i]);
		}
		for (int i = n-1; i >= 0; i--) {
			int low = 0;
			int high = n - 1;
			int mid = (low + high) / 2;
			while (low <= high) {
				if (ser1[mid] < a[i]) {
					low = mid + 1;
				} else {
					high = mid - 1;
				}
				mid = (low + high) / 2;
			}
			dec[i]=high+2;
			cur = Math.max(cur, high + 1);
			ser1[high + 1] = Math.min(ser1[high + 1], a[i]);
		}
		int ans=1;
		for (int i = 0; i < dec.length; i++) {
			ans=Math.max(ans, 2*Math.min(inc[i], dec[i])-1);
		}
		return ans;
	}
	
	
	public static void permutation(int idx,int v) {
		if(v==(1<<n)-1) {
			perm[x++]=pe.clone();
			return ;
		}
		for (int i = 0; i < n; i++) {
			if((v&1<<i)==0) {
				pe[idx]=aa[i];
				permutation(idx+1, v|1<<i);
			}
		}
		return ;
	}
	
	public static void pre2() {
		for (int i = 0; i < pow.length; i++) {
			long x=1l<<i;
			pow[i]=x+"";
		}
	}
		
	public static void sort(int[]a) {
		mergesort(a, 0, a.length-1);
	}
	
	public static void sortIdx(long[]a,long[]idx) {
		mergesortidx(a, idx, 0, a.length-1);
	}
	
	public static long C(int a,int b) {
		long x=fac[a];
		long y=fac[a-b]*fac[b];
		return x*pow(y,mod-2)%mod;
	}
	
	public static long pow(long a,long b) {
		long ans=1;a%=mod;
		for(long i=b;i>0;i/=2) {
			if((i&1)!=0)
				ans=ans*a%mod;
			a=a*a%mod;
		 }    
		    
		 return ans;
	}
	
	public static void pre(){
		fac[0]=1;
		fac[1]=1;
		fac[2]=1;
		for (int i = 3; i < fac.length; i++) {
			fac[i]=((fac[i-1]*2*i)/2)%mod;
		}
	}
	
	public static long eval(String s) {
		long p=1;
		long res=0;
		for (int i = 0; i < s.length(); i++) {
			res+=p*(s.charAt(s.length()-1-i)=='1'?1:0);
			p*=2;
		}
		return res;
	}
	
	public static String binary(long x) {
		String s="";
		while(x!=0) {
			s=(x%2)+s;
			x/=2;
		}
		return s;
	}
	
	public static boolean allSame(String s) {
		char x=s.charAt(0);
		for (int i = 0; i < s.length(); i++) {
			if(s.charAt(i)!=x)return false;
		}
		return true;
	}
	
	public static boolean isPalindrom(String s) {
		int l=0;
		int r=s.length()-1;
		while(l<r) {
			if(s.charAt(r--)!=s.charAt(l++))return false;
			
		}
		return true;
	}
	 
	
	public static boolean isSubString(String s,String t) {
		int ls=s.length();
		int lt=t.length();
		boolean res=false;
		for (int i = 0; i <=lt-ls; i++) {
			if(t.substring(i, i+ls).equals(s)) {
				res=true;
				break;
			}
		}
		return res;
	}
	
	public static boolean isSorted(long[]a) {
		for (int i = 0; i < a.length-1; i++) {
			if(a[i]>a[i+1])return false;
		}
		return true;
	}
	
	public static boolean isPrime(long n)
    {
 
        // Check if number is less than
        // equal to 1
        if (n <= 1)
            return false;
 
        // Check if number is 2
        else if (n == 2)
            return true;
 
        // Check if n is a multiple of 2
        else if (n % 2 == 0)
            return false;
 
        // If not, then just check the odds
        for (int i = 3; i <= Math.sqrt(n); i += 2)
        {
            if (n % i == 0)
                return false;
        }
        return true;
    }
	public static int whichPower(int x) {
		int res=0;
		for (int j = 0; j < 31; j++) {
			if((1<<j&x)!=0) {
				res=j;
				break;
			}
		}
		return res;
	}
 
	public static long evaln(String x,int n) {
		long res=0;
		for (int i = 0; i < x.length(); i++) {
			res+=Long.parseLong(x.charAt(x.length()-1-i)+"")*Math.pow(n, i);
		}
		return res;
	}
	static void merge(int[] arr,int b,int m,int e) {
		int len1=m-b+1,len2=e-m;
		int[] l=new int[len1];
		int[] r=new int[len2];
		for(int i=0;i<len1;i++)l[i]=arr[b+i];
		for(int i=0;i<len2;i++)r[i]=arr[m+1+i];
		int i=0,j=0,k=b;
		while(i<len1 && j<len2) {
			if(l[i]<r[j])arr[k++]=l[i++];
			else arr[k++]=r[j++];
		}
		while(i<len1)arr[k++]=l[i++];
		while(j<len2)arr[k++]=r[j++];
		return;
	}
	static void mergesortidx(long[] arr,long[]idx,int b,int e) {
		if(b<e) {
			int m=b+(e-b)/2;
			mergesortidx(arr,idx,b,m);
			mergesortidx(arr,idx,m+1,e);
			mergeidx(arr,idx,b,m,e);
		}
		return;
		
	}
	static void mergeidx(long[] arr,long[]idx,int b,int m,int e) {
		int len1=m-b+1,len2=e-m;
		long[] l=new long[len1];
		long[] lidx=new long[len1];
		long[] r=new long[len2];
		long[] ridx=new long[len2];
		for(int i=0;i<len1;i++) {
			l[i]=arr[b+i];
			lidx[i]=idx[b+i];
		}
		for(int i=0;i<len2;i++) {
			r[i]=arr[m+1+i];
			ridx[i]=idx[m+1+i];
		}
		int i=0,j=0,k=b;
		while(i<len1 && j<len2) {
			if(l[i]<=r[j]) {
				arr[k++]=l[i++];
				idx[k-1]=lidx[i-1];
			}
			else {
				arr[k++]=r[j++];
				idx[k-1]=ridx[j-1];
			}
		}
		while(i<len1) {
			idx[k]=lidx[i];
			arr[k++]=l[i++];
		}
		while(j<len2) {
			idx[k]=ridx[j];
			arr[k++]=r[j++];
		}
		return;
	}
	static void mergesort(int[] arr,int b,int e) {
		if(b<e) {
			int m=b+(e-b)/2;
			mergesort(arr,b,m);
			mergesort(arr,m+1,e);
			merge(arr,b,m,e);
		}
		return;
		
	}
	
	static long mergen(int[] arr,int b,int m,int e) {
		int len1=m-b+1,len2=e-m;
		int[] l=new int[len1];
		int[] r=new int[len2];
		for(int i=0;i<len1;i++)l[i]=arr[b+i];
		for(int i=0;i<len2;i++)r[i]=arr[m+1+i];
		int i=0,j=0,k=b;
		long c=0;
		while(i<len1 && j<len2) {
			if(l[i]<r[j])arr[k++]=l[i++];
			else {
				arr[k++]=r[j++];
				c=c+(long)(len1-i);
			}
		}
		while(i<len1)arr[k++]=l[i++];
		while(j<len2)arr[k++]=r[j++];
		return c;
	}
	static long mergesortn(int[] arr,int b,int e) {
		long c=0;
		if(b<e) {
			int m=b+(e-b)/2;
			c=c+(long)mergesortn(arr,b,m);
			c=c+(long)mergesortn(arr,m+1,e);
			c=c+(long)mergen(arr,b,m,e);
		}
		return c;
		
	}
	public static long fac(int n) {
		if(n==0)return 1;
		return n*fac(n-1);
	}
	public static long gcd(long a, long b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
     
	public static long summ(long x) {
		long sum=0;
		while(x!=0) {
			sum+=x%10;
			x=x/10;
		}
		return sum;
				
	}
	
	public  static ArrayList<Integer> findDivisors(int n){
	        ArrayList<Integer>res=new ArrayList<Integer>();
	        for (int i=1; i<=Math.sqrt(n); i++)
	        {
	            if (n%i==0)
	            {
	                // If divisors are equal, print only one
	                if (n/i == i)
	                	res.add(i);
	                else {
	                	res.add(i);
	                	res.add(n/i);
	                }	
	            }
	        }
	        return res;
	    }

	
	public static void sort2darray(Integer[][]a){
		Arrays.sort(a,Comparator.<Integer[]>comparingInt(x -> x[0]).thenComparingInt(x -> x[1]));
 
	}
	
	
	
		
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
		public Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
		public boolean ready() throws IOException {
			return br.ready();
		}
		public int[] nextArrint(int size) throws IOException {
			int[] a=new int[size];
			for (int i = 0; i < a.length; i++) {
				a[i]=sc.nextInt();
			}
			return a;
		}
		public long[] nextArrlong(int size) throws IOException {
			long[] a=new long[size];
			for (int i = 0; i < a.length; i++) {
				a[i]=sc.nextLong();
			}
			return a;
		}
		public int[][] next2dArrint(int rows,int columns) throws IOException{
			int[][]a=new int[rows][columns];
			for (int i = 0; i < rows; i++) {
				for (int j = 0; j < columns; j++) {
					a[i][j]=sc.nextInt();
				}
			}
			return a;
		}
		public long[][] next2dArrlong(int rows,int columns) throws IOException{
			long[][]a=new long[rows][columns];
			for (int i = 0; i < rows; i++) {
				for (int j = 0; j < columns; j++) {
					a[i][j]=sc.nextLong();
				}
			}
			return a;
		}
	}
	
	static class Side{
		Point a;
		Point b;
		public Side(Point a,Point b) {
			this.a=a;
			this.b=b;
		}
		@Override
		public boolean equals(Object obj) {
			Side s=(Side)obj;
			return (s.a.equals(a)&&s.b.equals(b))||(s.b.equals(a)&&s.a.equals(b));
		}
		@Override
		public String toString() {
			
			return "("+a.toString()+","+b.toString()+")";
		}
	}
	static class Point{
		int x;
		int y;
		int z;
		public Point(int x,int y,int z) {
			this.x=x;
			this.y=y;
			this.z=z;
		}
		@Override
		public boolean equals(Object obj) {
			Point p=(Point)obj;
			return x==p.x&&y==p.y&&z==p.z;
		}
		@Override
		public String toString() {
			return "("+x+","+y+","+z+")";
		}
	}
	static class Pair implements Comparable{
		long x;
		long y;
		public Pair(long x,long y) {
			this.x=x;
			this.y=y;
		}
		@Override
		public boolean equals(Object obj) {
			Pair p=(Pair)obj;
			return x==p.x&&y==p.y;
		}
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return "("+x+","+y+")";
		}
		
		@Override
		public int compareTo(Object o) {
			Pair p=(Pair)o;
			return x>p.x?1:x==p.x?0:-1;
		}
	}
	static class sPair{
		String s;
		Pair p;
		public sPair(String s,Pair p) {
			this.p=p;
			this.s=s;
		}
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return s+" "+p;
		}
	}
	static Scanner sc=new Scanner(System.in);
	static PrintWriter pw=new PrintWriter(System.out);
}