You have been given stock values/prices for N number of days. Every i-th day signifies the price of a stock on that day. Your task is to find the maximum profit which you can make by buying and selling the stocks.
You may make as many transactions as you want but can not have more than one transaction at a time i.e, if you have the stock, you need to sell it first, and then only you can buy it again.
Input format :
The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case or query contains an integer 'N' representing the total number of days for which you have stock prices.
The second line contains 'N' single space-separated integers representing the price of the stock on i-th day.
Output Format :
For each test case, print the maximum profit that you can earn.
Output for every test case will be printed in a separate line.
You are not required to print anything explicitly. Just implement the function.
1 <= t <= 10^2
0 <= N <= 10^5
Time Limit: 1 sec
Sample Input 1 :
1 2 3 4 5 6 7
Sample Output 1 :
We can make the maximum profit by buying the stock on the first day and selling it on the last day.
Sample Input 2 :
7 6 5 4 3 2 1
Sample Output 2 :
We can make the maximum profit by not buying the stock.