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 javax.swing.text.Segment;

import java.io.*;
import java.math.*;
import java.sql.Array;



public class Main {
	  static class Scanner{
		  
			BufferedReader br;
			StringTokenizer st;
			public Scanner() {
				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 long mod = (long)(1e9 + 7);
	 
	static void sort(long[] arr ) {
		 ArrayList<Long> al = new ArrayList<>();
		 for(long e:arr) al.add(e);
		 Collections.sort(al);
		 for(int i = 0 ; i<al.size(); i++) arr[i] = al.get(i);
	 }
	static void sort(int[] arr ) {
		 ArrayList<Integer> al = new ArrayList<>();
		 for(int e:arr) al.add(e);
		 Collections.sort(al);
		 for(int i = 0 ; i<al.size(); i++) arr[i] = al.get(i);
	 }
	static void sort(char[] arr) {
		ArrayList<Character> al = new ArrayList<Character>();
		for(char cc:arr) al.add(cc);
		Collections.sort(al);
		for(int i = 0 ;i<arr.length ;i++) arr[i] = al.get(i);
	}
	static void rvrs(int[] arr) {
		int i =0 , j = arr.length-1;
		while(i>=j) {
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}
	}
	static void rvrs(long[] arr) {
		int i =0 , j = arr.length-1;
		while(i>=j) {
			long temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}
	}

	static long mod_mul(long a , long b ,long mod) {
		return ((a%mod)*(b%mod))%mod;
	}
	 static long gcd(long a, long b)
	  {      
	     if (b == 0)
	        return a;
	     return gcd(b, a % b); 
	  }
	 static boolean[] prime(int num) {
			boolean[] bool = new boolean[num];
		     
		      for (int i = 0; i< bool.length; i++) {
		         bool[i] = true;
		      }
		      for (int i = 2; i< Math.sqrt(num); i++) {
		         if(bool[i] == true) {
		            for(int j = (i*i); j<num; j = j+i) {
		               bool[j] = false;
		            }
		         }
		      }
		      if(num >= 0) {
		    	  bool[0] = false;
		    	  bool[1] = false;
		      }
		      
		      return bool;
		}

	 static long modInverse(long a, long m)
	    {
	        long g = gcd(a, m);
	       
	          return   power(a, m - 2, m);
	        
	    }
	   static long lcm(long a , long b) {
		   return (a*b)/gcd(a, b);
	   }
	   static int lcm(int a , int b) {
		   return (int)((a*b)/gcd(a, b));
	   }
	 static long power(long x, long y, long m){
	        if (y == 0) return 1; long p = power(x, y / 2, m) % m; p = (int)((p * (long)p) % m);
	        if (y % 2 == 0) return p; else return (int)((x * (long)p) % m); }
	   
     static class Combinations{
	    	 private long[] z;
	    	 private long[] z1;
	    	 private long[] z2;
	    	  public Combinations(long N , long mod) {
				z = new long[(int)N+1];
				z1 = new long[(int)N+1];
				z[0] = 1;
				for(int i =1 ; i<=N ; i++) z[i] = (z[i-1]*i)%mod;
			     z2 = new long[(int)N+1];
				z2[0] = z2[1] = 1;
			    for (int i = 2; i <= N; i++)
			        z2[i] = z2[(int)(mod % i)] * (mod - mod / i) % mod;
			    
			    
			    z1[0] = z1[1] = 1;
			    
			    for (int i = 2; i <= N; i++)
			        z1[i] = (z2[i] * z1[i - 1]) % mod;
			}
	    	  long fac(long n) {
	    		  return z[(int)n];
	    	  }
	    	  long invrsNum(long n) {
	    		  return z2[(int)n];
	    	  }
	    	  long invrsFac(long n) {
	    		  return invrsFac((int)n);
	    	  }
	    	  long ncr(long N, long R, long mod)
	    	  {		if(R<0 || R>N ) return 0;
	    		    long ans = ((z[(int)N] * z1[(int)R])
	    		              % mod * z1[(int)(N - R)])
	    		             % mod;
	    		    return ans;
	    		}
	      }
	      static class DisjointUnionSets {
			    int[] rank, parent;
			    int n;
			  
			    public DisjointUnionSets(int n)
			    {
			        rank = new int[n];
			        parent = new int[n];
			        this.n = n;
			        makeSet();
			    }
			  
			    void makeSet()
			    {
			        for (int i = 0; i < n; i++) {
			          
			            parent[i] = i;
			        }
			    }
			  
			    int find(int x)
			    {
			        if (parent[x] != x) {
			        
			            parent[x] = find(parent[x]);
			  
			        }
			  
			        return parent[x];
			    }
			  
			    void union(int x, int y)
			    {
			        int xRoot = find(x), yRoot = find(y);
			  
			        if (xRoot == yRoot)
			            return;
			  
			        if (rank[xRoot] < rank[yRoot])
			  
			            parent[xRoot] = yRoot;
			  
			        else if (rank[yRoot] < rank[xRoot])
			  
			            parent[yRoot] = xRoot;
			  
			        else
			        {
			            parent[yRoot] = xRoot;
			  
			            rank[xRoot] = rank[xRoot] + 1;
			        }
			    }
			}
	      static int max(int a , int b) {
	    	  if(b>a) return b;
	    	  return a;  
	      }
	      static long max(long a , long b) {
	    	  if(b>a) return b;
	    	  return a;  
	      }
	      static int min(int a , int b) {
	    	  if(b<a) return b;
	    	  return a;
	      }
	      static long min(long a , long b) {
	    	  if(b<a) return b;
	    	  return a;
	      }
	      static int[] KMP(String str) {
	    	  int n = str.length();
	    	  int[] kmp = new int[n];
	    	  for(int i = 1 ; i<n ; i++) {
	    		  int j = kmp[i-1];
	    		  while(j>0 && str.charAt(i) != str.charAt(j)) {
	    			  j = kmp[j-1];
	    		  }
	    		  if(str.charAt(i) == str.charAt(j)) j++;
	    		  kmp[i] = j;
	    	  }
	    	  
	    	  return kmp;
	      }
	      
	      
/************************************************ Query **************************************************************************************/	  
	 
/***************************************** 		Sparse Table	********************************************************/
	      static class SparseTable{
	    		
	    		private long[][] st;
	    		
	    		SparseTable(long[] arr){
	    			int n = arr.length;
	    			st = new long[n][25];
	    			log = new int[n+2];
	    			build_log(n+1);
	    			build(arr);
	    		}
	    		
	    		private void build(long[] arr) {
	    			int n = arr.length;
	    			
	    			for(int i = n-1 ; i>=0 ; i--) {
	    				for(int j = 0 ; j<25 ; j++) {
	    					int r = i + (1<<j)-1;
	    					if(r>=n) break;
	    					if(j == 0 ) st[i][j] = arr[i];
	    					else st[i][j] = Math.max(st[i][j-1] , st[ i + ( 1 << (j-1) ) ][ j-1 ] );
	    				}
	    			}
	    		}
	    		public long gcd(long a  ,long b) {
	    			if(a == 0) return b;
	    			return gcd(b%a , a);
	    		}
	    		public long query(int l ,int r) {
	    			int w = r-l+1;
	    			int power = log[w];
	    			return Math.max(st[l][power],st[r - (1<<power) + 1][power]);
	    		}
	    		private int[] log;
	    		void build_log(int n) {
	    			log[1] = 0;
	    			for(int i = 2 ; i<=n ; i++) {
	    				log[i] = 1 + log[i/2];
	    			}
	    		}
	    	}
	      
	      
/********************************************************	Segement Tree	*****************************************************/
/**
	 	 static class SegmentTree{
			 long[] tree;
			 long[] arr;
			 int n;
			 SegmentTree(long[] arr){
				 this.n = arr.length;
				 tree = new long[4*n+1];
				 this.arr = arr;
				 buildTree(0, n-1, 1);
			 }
			 
			 
			  void buildTree(int s ,int e  ,int index ) {
					if(s == e) {
						tree[index] = arr[s];
						return;
					}
				
					int mid = (s+e)/2;
					
					buildTree( s,  mid, 2*index);
					buildTree( mid+1, e, 2*index+1);
					
					tree[index] = Math.min(tree[2*index] , tree[2*index+1]);
				}
			  
			 long query(int si ,int ei) {
				 return query(0 ,n-1 , si ,ei , 1   );
			 }
			 private long query( int ss ,int se ,int qs , int qe,int index) {
					
					if(ss>=qs && se<=qe) return tree[index];
					
					if(qe<ss || se<qs) return (long)(1e17);
					
					int mid = (ss + se)/2;
					long left = query( ss , mid , qs ,qe , 2*index);
					long right= query(mid + 1 , se , qs ,qe , 2*index+1);
					return Math.min(left, right);
				}
			 public void update(int index , int val) {
				 arr[index] = val;
				 for(long e:arr) System.out.print(e+" ");
				 update(index , 0 , n-1 , 1);
			 }
			 private void update(int id ,int si , int ei , int index) {
				 if(id < si || id>ei) return;
				 if(si == ei ) { 
					 tree[index] = arr[id];
					 return;
				 }
				 if(si > ei) return;
				 int mid = (ei + si)/2;
					
					update( id,  si, mid , 2*index);
					update( id , mid+1, ei , 2*index+1);
					
					tree[index] = Math.min(tree[2*index] ,tree[2*index+1]);
			 }
			  
		 }
		 */

/* ***************************************************************************************************************************************************/	 
	 
	      static Scanner sc = new Scanner();
	 static StringBuilder sb = new StringBuilder();
	 public static void main(String args[]) throws IOException {

		 int tc = 1;
		  tc = sc.nextInt();
		
		 for(int i = 1 ; i<=tc ; i++) {

//			 sb.append("Case #" + i + ": "  );	// During KickStart && HackerCup
			 TEST_CASE();
			  
		 }
		 System.out.println(sb);
	 }

	 static void TEST_CASE() {
		 int n = sc.nextInt();
		 long[] arr = new long[n];
		for(int i = 0 ; i<n ; i++)
			arr[i] = sc.nextLong();
		sort(arr);
		long[] suf = new long[n];
		suf[n-1] = arr[n-1];
		for(int i = n-2 ; i>=0 ; i--) {
			suf[i] = arr[i] + suf[i+1];
		}
		long max = arr[n-1];
		for(int i = n-2 ; i>=0 ;i--) {
			max = Math.max(max,suf[i] );
		}
		sb.append(max+"\n");
	 }
}

	 

/*******************************************************************************************************************************************************/

/**
	
	
 */

 

