Maximize Stock Profit

In this problem, you are given a series of stock prices for consecutive days. Your task is to determine the maximum profit that can be achieved by performing exactly one transaction (i.e., buying once and selling once later). If there is no possibility of making a profit, return 0.

You are given t test cases. For each test case, the first number represents the number of stock prices, followed by that many integers representing the price on each day.

The profit for a given test case is calculated as:

$$profit = price_{sell} - price_{buy}$$

where price_buy is the price on the day you buy the stock and price_sell is the price on a day after the purchase. You need to maximize this profit. The problem guarantees that you can only perform at most one transaction.

Example:

• Input: 6 7 1 5 3 6 4
• Output: 5

inputFormat

The input is read from stdin and has the following format:

t
n1
price1 price2 ... pricen1
n2
price1 price2 ... pricen2
...
nt
price1 price2 ... pricent

Here, t denotes the number of test cases. For each test case, n is the number of stock prices, followed by n space-separated integers representing the prices for consecutive days.

outputFormat

The output should be written to stdout and for each test case, output the maximum profit on a new line.

## sample

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

5
0

</p>