题目描述

薯条哥最喜欢的运动是骑自行车，因此她决定在本地的小山上做一次旅行。

她骑自行车的路线可以描述为$n$个数字的数列，每个数字表示每一段路地海拔高度。

薯条哥最感兴趣的是最长的高度一直上升的子序列，她称这一段路为爬坡，薯条哥只想考虑这段爬坡的高度差（即开始和最后的数字的差距），而不是什么路程长度。

一段爬坡路被定义为长度至少为 2 的连续的非下降子数列。

例如，我们考虑如下路线数列 12 3 5 7 10 6 1 11，这里有两个爬坡，第一个爬坡（3 5 7 10）的高度差是 7，第二个爬坡的高度差是 10（1 11）。

帮助薯条哥计算高度差最大的爬坡的高度差。

输入描述

输入包含多组测试数据。

第一行输入一个整肃$T$，表示测试数据的组数。

接下来，每组数据第一行包含一个整数$n(1\le n\le 10^5)$，表示路线数列的长度。

第二行包含$n$个整数$p_1,p_2,…,p_n(1\le p_i\le 10^9)$表示路线数列。

保证所有的样例的数列总长度不会超过$10^5$。

输出描述

每组数据输出一行结果，表示最大高度差。

如果不存在爬坡，则输出 0。

样例

输入

2
5
1 2 1 4 6
6
10 8 8 6 4 3

输出

5
0