SP19382 STK - Stock

Alex heard a lot about investing in the stock market and now wants to do it to earn some profit. Being a new investor he is scared of the risks in the stock market, so he decides that at any instance he will not have more than one stock with him. It is also decided that on a particular day he can either buy or sell atmost one stock(only one transaction allowed). Now given the prices of one particular stock over the period of n days Alex decides he will make atmost k buys and k sells. Alex heard a lot about investing in the stock market and now wants to do it to earn some profit. Being a new

First line contains an integer T(

For each test case output one line stating the maximum profit.