Buffalo Marketing

Gopal wants to make some money from buffalos, but in a quite a different way. He decided that his future lay in speculating on buffalos. In the market in his village, buffalos were bought and sold everyday. The price fluctuated over the year, but on any single day the price was always the same.

   He decided that he would buy buffalos when the price was low and sell them when the price was high and, in the process, accummulate great wealth.But for each day only following operations are allowed.

buy one buffalo.
sale all buffaloes that he owns
do nothing

Help gopal to get maximum amount of money.

Input

First line contains T, number of testcases.
First line each test case contains Number of days,N, Next line contains N integers cost of buffallo each day

Output
For each test case output single line contaning the solution as single integer.

Constrains

1 <= T <= 10
1 <= N <= 5*10^4
1 <= Cost <= 10^5
Time limit:1s

Sample Input

2
3
1 2 90
4
1 3 1 2

Sample Output

177
3

Explanation

For the First case, you can buy one buffaloe on the first two days, and sell both of them on the third day.
For the Second case, you can buy one buffaloe on day 1, sell one on day 2, buy one buffaloe on day 3, and sell it on day 4

见题面

见题面