C. Cryptocurrency
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Many of you know Yessine, but very few know that he is a very successful entrepreneur. In fact, he founded his start-up Iceberg Corporation, specialized in cryptocurrency, a few years ago. He is currently a millionaire, but he keeps going to INSAT so he can compete at the ICPC regionals.

As time went on, Yessine's schedule has gotten really busy, so he decided to hire his first employee. He hired his friend Oussama to do the job of a software engineer, a data scientist, and a business analyst while paying him minimal wage. Oussama was very motivated to work, so he didn't care about the money; he just wanted to solve hard problems. One time he was analyzing the evaluation of the cryptocurrency market and came across the following problem:

Given a sequence $$$A$$$ of $$$N$$$ numbers denoting the prices of a certain cryptocurrency over a period of time, find the highest contiguous increase in price (HCI). The HCI is the largest possible difference between the last and first element over all contiguous increasing subsequences.

* A contiguous subsequence $$$A_{i}, A_{i+1},A_{i+2},\dots,A_j$$$ is an increasing sequence if it satisfies $$$A_i \lt A_{i+1} \lt A_{i+2} \lt ... \lt A_j$$$.

Can you solve this problem ?

Input

The first line contains the number of testcases $$$1 \le T\le 100$$$.

The first line of each testcase contains an integer $$$N$$$ ($$$ 1\le N \le10^5 $$$) denoting the length of the sequence.

The second line of each testcase contains $$$N$$$ integers denoting the sequence $$$A$$$ ($$$ 0 \le A_i \le 10^9 $$$).

It is guaranteed that the sum of $$$N$$$ over all testcases doesn't exceed $$$10^{6}$$$.

Output

Print a single integer : the highest contiguous increase of the cryptocurrency.

Example
Input
4
4
1 2 3 4
4
4 3 2 1
4
1 3 2 4
4
1 2 2 4
Output
3
0
2
2