Maximum Profit

You are given a sequence of prices, where the i-th price represents the price of a product on day i. Your task is to determine the maximum profit that can be obtained by choosing a day to buy and a later day to sell the product. If no profit is possible, output 0.

Formally, you are given an array of prices \(p_1, p_2, \dots, p_n\). Find the maximum value of \(p_j - p_i\) for \(1 \le i < j \le n\). If no such pair exists, the maximum profit is \(0\).

inputFormat

The first line contains an integer T, the number of test cases. For each test case, the first line contains an integer n, the number of days. The next line contains n space-separated integers representing the prices on each day.

outputFormat

For each test case, output a single line containing the maximum profit that can be achieved.## sample

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

5
0