Stock

Hongjun is deep into the stock market these days. He has a sharp eye for the future, so the price he predicts for each day always turns out to be right. Every day he does exactly one of the following.

1. Buy one share.
2. Sell as many of the shares he holds as he wants.
3. Do nothing.

Knowing every future price is not the same as knowing how to trade. Given the price on each day, compute the largest profit Hongjun can make.

For example, if there are 3 days and the prices are 10, 7, 6, the price only falls and the largest profit is 0. If the prices are 3, 5, 9, he buys one share on each of the first two days and sells both on the last day for a profit of 10.

The first line contains the number of test cases $T$. For each test case, the first line contains the number of days $N$ ($2 \le N \le 10^6$), and the second line contains the $N$ prices in day order, separated by spaces. Every price is a natural number of at most $10\,000$.

For each test case, print the largest profit on its own line. The answer fits in a signed 64-bit integer.