再炒股票

Time Limit : 1 Second

Memory Limit : 256 MB

Submission: 65

Solved: 14

Description

最近股市又涨了!你呆呆地看着上半年的股价波动,心理盘算着,当初要是买了股票,可以挣多少钱啊!


求进行2次交易做多可以获得的利润,


一次交易定义为先买1股,再卖出这1股。



由于资金有限,第1次交易卖出以后才可以进行第二次交易的买入。

Input

第一行是一个整数M,表示一共有M个测试样例。



每个测试样例的第一行是一个整数N,表示有N天的股票价格数据。接着是一行N个空格分隔的整数,P[i]表示某股票第i天的价格(元/股)。



M<=100,N<=10000,0<P[i]<=10000

Output

每次测试样例输出一行,每行包含一个整数,表示最大获利值。    

sample input
2
5
3 9 8 6 4
4
6 9 2 3
sample output
6
4
hint
source
© 2015 HUST ACMICPC TEAM. All Right Reserved.