To be The Elden Lord, The Tarnished will face many challenges. Here comes one.
There is a monster tower of height , the strength of the monster on the -th floor is . The initial strength of The Tarnished is .
For any moment, The Tarnished can choose some monster not stronger than him from the lowest floors, and kill it. After The Tarnished kills the monster on the -th floor, his strength increases by , and the -th floor will disappear. So all floors higher than the -th floor will fall, the original -th floor become the -th floor, -th becomes -th, and so on.
Now, the problem is what is the minimum  to kill all monsters in this tower.

The first line contains a single integer  --- the number of test cases.
The first line of each test case contains two integers  and  --- the height of the tower and the highest floor that The Tarnished can reach respectively.
The second line of each test case contains  integers  --- the strength of each monster.
It is guaranteed that  over all test cases.

For each test case, output a single integer --- the minimum  to kill all monsters.

2
3 2
1 10 5
3 1
1 10 5

4
9

In the first test case, The Tarnished kills the monster on the first floor, so his strength becomes , and the third floor becomes the second floor so The Tarnished can reach it and kill the monster. After that, his strength becomes  and can kill the last one.