Maximum Profit

In this problem, you are given the stock prices over several days. Your task is to determine the maximum profit obtainable with at most one transaction (i.e. one buy followed by one sell). Formally, for a given sequence of prices (p_1, p_2, \dots, p_n), you need to compute the maximum value of (p_j - p_i) for (1 \le i < j \le n). If no profit can be made, output (0).

inputFormat

The input begins with an integer (T) representing the number of test cases. Each test case consists of two lines. The first line contains an integer (n), the number of days. The second line contains (n) space-separated integers representing the stock prices on consecutive days.

outputFormat

For each test case, output a single integer on its own line representing the maximum profit achievable with one buy-sell transaction. If no profit is possible, output (0).## sample

3
6
7 1 5 3 6 4
4
7 6 4 3
5
1 2 3 4 5

5
0
4