Description

琪露诺有一个由N个正整数组成的数字序列，她可以对数组做以下操作一次：选择此数组的字段，将其循环旋转任意次数。 也就是说，她可以对数组做一次以下操作： 1.选择两个整数l和r，1≤𝑙≤𝑟≤𝑛，和一个任意的正整数k。 2.重复执行k次：让A𝑙=A𝑙+1,A𝑙+1=A𝑙+2,…,A𝑟−1=A𝑟,A𝑟=A𝑙。（所有更改同时发生）。 琪露诺想通过这样的一次操作使得An-A1的值最大。现在，请你编写一个程序计算，琪露诺能获得的最大值是多少。

Format

Input

第一行，一个整数q，1≤𝑞≤50，表示q组测试数据。 每组测试数据有两行。 每组第一行一个整数n，表示序列的长度（n<=2000） 每组第二行N个整数Ai，（Ai<=999）

Output

每组测试数据输出一个整数，表示琪露诺能获得的最大值。

Samples

3
6
1 3 9 11 5 7
1
20
3
9 99 999

10
0
990

Limitation

1s, 1024KiB for each test case.