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

public class Main
{
	static String shengxiao[] =
	{ "ox", "tiger", "rabbit", "dragon", "snake", "horse", "goat", "monkey", "rooster", "dog", "pig", "rat" };
	static String shengxiaoo[] =
	{ "Ox", "Tiger", "Rabbit", "Dragon", "Snake", "Horse", "Goat", "Monkey", "Rooster", "Dog", "Pig", "Rat" };
	static int zhong[] =
	{ -1, 1, 0, 0, -1, -1, 1, 1 };
	static int heng[] =
	{ 0, 0, -1, 1, -1, 1, -1, 1 };
	static int zhongg[] =
	{ -1, -1, 0, 1, 1, 1, 0, -1 };
	static int hengg[] =
	{ 0, 1, 1, 1, 0, -1, -1, -1 };
	static int month[] =
	{ 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
	static int inf = Integer.MAX_VALUE;
	static long inff = Long.MAX_VALUE;

	static int N = (int) 5e1;
	static int M = (int) 1e5;
	static int mod = 19990920;

//	 提交时注意需要注释掉首行package
//	 基础类型数组例如long[]使用Arrays排序容易TLE,可以替换成Long[]
//	 int 最大值 2^31 - 1 , 2147483647;
//	 尽量使用long类型,避免int计算的数据溢出

	static void init()
	{

	}

//	static void solve(String s)
//	static void solve(int n)
//	static void solve(long n)
	static void solve() throws FileNotFoundException
	{
		int n = sc.readInt();
		long shu[] = new long[n];
		for (int i = 0; i < n; i++)
			shu[i] = sc.readLong();

		Arrays.sort(shu);
		long max = shu[0];
		for (int i = 1; i < n; i++)
		{
			max = Math.max(max, shu[i] - shu[i - 1]);
		}
		out.printLine(max);
	}

	public static void main(String[] args) throws FileNotFoundException
	{
//		init();
//
		int t = 1;
//		int t = sc.readInt();
		for (int i = 1; i <= t; i++)
			solve();

		out.close();
	}

	static InputStream inputStream = System.in;
	static OutputStream outputStream = System.out;
	static InputReader sc = new InputReader(inputStream);
	static OutputWriter out = new OutputWriter(outputStream);

//	System.setIn(new FileInputStream("copycat.in"));// 读入文件
//	System.setOut(new PrintStream(new FileOutputStream("copycat.out")));// 输出到文件
//	long startTime = System.currentTimeMillis(); // 获取开始时间
//	long endTime = System.currentTimeMillis(); // 获取结束时间
//	System.out.println("程序运行时间：" + (endTime - startTime) + "ms"); // 输出程序运行时间

//	int a = sc.readInt();// 整型
//	long b = sc.readLong();// 长整型
//	double c = sc.readDouble();// 双精度
//	String d = sc.readString(); // 一个字符串
//	String e = sc.readStringLine();// 一行字符串
//	char f = sc.readCharacter();// 单个字符
//	out.print();
//	out.printLine();
//	out.close();

	// 封装基于字节流读取的高效输入类InputReader，避免Scanner的低效率，比streamTokenizer快读还快；
	static class InputReader
	{
		// java.io.InputStream 所有字节输入流的父类
		private InputStream stream;
		// 输入缓存byte数组
		private byte[] buf = new byte[1024];
		private int curChar;// 当前字符
		private int numChars;// 总输入字符
		// 自定义接口
		private SpaceCharFilter filter;

		// 构造函数
		public InputReader(InputStream stream)
		{
			this.stream = stream;
		}

		// 尝试至少读取一个字节并存储到缓冲数组buf中
		public int read()
		{
			if (numChars == -1)
				throw new InputMismatchException();
			// 既然是缓冲读取，如果1次读取1024个，那么每次直接缓冲区读取 如果curChar<numChar 那么证明缓冲区的还没有用完
			if (curChar >= numChars)
			{
				curChar = 0;// 缓冲区的数据用完了，那么从0开始，再去一次性读取若干个放到缓冲数组里
				try
				{
					// 从输入流中读取一定数量的字节，并将其存储在缓冲区数组buf中，numChar等于实际读取的字节数量
					numChars = stream.read(buf);
				} catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (numChars <= 0)// 如果读取的有效数量为0，那么返回-1，巧妙的避开了合法的ASCII码
					return -1;
			}
			// 等价于else (curChar<numChar),如果缓冲区没有用完，直接返回缓冲区当前第curChar字符，指针后移
			return buf[curChar++];
		}

		// 读入一个一个字节，手工构造int
		public int readInt()
		{
			int c = read();
			while (isSpaceChar(c))// 忽略>=1的所有空格符或者自己定义的不能构成整数的无意义符号入\n\r\t等
				c = read();
			int sgn = 1;// 识别第一符号位，判定是正数还是负数
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// 不断的*10+当前数构成int的判断
			return res * sgn;
		}

		// 读入一个一个字节，手工构造long
		public long readLong()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			long res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		// 高效的读取字符串
		public String readString()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				// 确定指定的代码点是否是一个有效的Unicode代码点值
				if (Character.isValidCodePoint(c))
					res.appendCodePoint(c);// 追加Unicode代码点值
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		// 统一Scanner的语法习惯
		public String next()
		{
			return readString();
		}

		// 读入一行字符串数组
		public static String[] readStringArray(InputReader in, int size)
		{
			String[] array = new String[size];
			for (int i = 0; i < size; i++)
				array[i] = in.readString();
			return array;
		}

		// 读入二维字符数组
		public static String[][] readStringTable(InputReader in, int rowCount, int columnCount)
		{
			String[][] table = new String[rowCount][];
			for (int i = 0; i < rowCount; i++)
				table[i] = readStringArray(in, columnCount);
			return table;
		}

		// 读入char
		public char readCharacter()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			return (char) c;
		}

		// 读入一行字符串
		public String readStringLine()
		{
			int c = read();
			while (isSpaceChar2(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				// 确定指定的代码点是否是一个有效的Unicode代码点值
				if (Character.isValidCodePoint(c))
					res.appendCodePoint(c);// 追加Unicode代码点值
				c = read();
			} while (!isSpaceChar2(c));
			return res.toString();
		}

		// 读入double
		public double readDouble()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.')
			{
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, readInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.')
			{
				c = read();
				double m = 1;
				while (!isSpaceChar(c))
				{
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, readInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}

		public boolean isSpaceChar(int c)
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return isWhitespace(c);
		}

		public boolean isSpaceChar2(int c)
		{
			if (filter != null)
				return filter.isSpaceChar2(c);
			return isWhitespace2(c);
		}

		// 可以输入空格的一行
		public static boolean isWhitespace2(int c)
		{
			return c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public static boolean isWhitespace(int c)
		{
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		// 自定义接口，定了一个抽象方法判断是否是空格符
		public interface SpaceCharFilter
		{
			public boolean isSpaceChar(int ch);

			public boolean isSpaceChar2(int ch);
		}
	}

	static class OutputWriter
	{
		// 向文本输出流打印对象的格式化表现形式 extends java.io.Writer
		private final PrintWriter writer;

		public OutputWriter(OutputStream outputStream)
		{
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}

		// 打印数组用空格分隔
		public void print(int[] array)
		{
			for (int i = 0; i < array.length; i++)
			{
				if (i != 0)
					writer.print(' ');
				writer.print(array[i]);
			}
		}

		// 带换行的数组打印
		public void printLine(int[] array)
		{
			print(array);
			writer.println();
		}

		public void print(Object... objects)
		{
			for (int i = 0; i < objects.length; i++)
			{
				if (i != 0)
					writer.print(' ');
				writer.print(objects[i]);
			}
		}

		public void printLine(Object... objects)
		{
			print(objects);
			writer.println();
		}

		public void close()
		{
			writer.close();
		}

		public void print(int i)
		{
			writer.print(i);
		}

		public void print(String i)
		{
			writer.print(i);
		}

		public void print(long i)
		{
			writer.print(i);
		}

		public void print(char i)
		{
			writer.print(i);
		}

		public void printf(String format, Object... x)
		{
			writer.printf(format, x);
		}

		// 打印带换行的整数i
		public void printLine(int i)
		{
			writer.println(i);
		}

		public void printLine(long i)
		{
			writer.println(i);
		}
	}

	static class IOUtils
	{
		// 高效读入整型一维数组
		public static int[] readIntArray(InputReader in, int size)
		{
			int[] array = new int[size];
			for (int i = 0; i < size; i++)
				array[i] = in.readInt();
			return array;
		}

		// 调用上面的读入一维数组的快速读取二维数组
		public static int[][] readIntTable(InputReader in, int rowCount, int columnCount)
		{
			int[][] table = new int[rowCount][];
			for (int i = 0; i < rowCount; i++)
				table[i] = readIntArray(in, columnCount);
			return table;
		}

		// 相当于二维数组（多关键字参数的另外一种写法）
		public static void readIntArrays(InputReader in, int[]... arrays)
		{
			for (int i = 0; i < arrays[0].length; i++)
			{
				for (int j = 0; j < arrays.length; j++)
					arrays[j][i] = in.readInt();
			}
		}

		public static char[] readCharArray(InputReader in, int size)
		{
			char[] array = new char[size];
			for (int i = 0; i < size; i++)
				array[i] = in.readCharacter();
			return array;
		}

		public static char[][] readTable(InputReader in, int rowCount, int columnCount)
		{
			char[][] table = new char[rowCount][];
			for (int i = 0; i < rowCount; i++)
				table[i] = readCharArray(in, columnCount);
			return table;
		}

	}

	static class MiscUtils
	{
		public static void decreaseByOne(int[]... arrays)
		{
			for (int[] array : arrays)
			{
				for (int i = 0; i < array.length; i++)
					array[i]--;
			}
		}

	}

}
