There are n hens in a farm. The egg hatching ability of all the hens decreases by 1 day after each time they hatch an egg. (i.e. every hen will hatch the next egg 1 day slower than the time it took to hatch the previous egg)

Let the initial egg hatching ability of Hen[i] be D[i].

• Hen[i] lays it's first egg on D[i]th day.
• Hen[i] lays it's second egg on 2*D[i]+1 th day.
• Hen[i] lays it's thrid egg on 3*D[i]+3rd day.
• Hen[i] lays it's fourth egg on 4*D[i]+6th day.
• Hen[i] lays it's fifth egg on 5*D[i]+10th day.

and so on..

Given n - the number of hens and the array D - the initial egg hatching ability of the hens, find the minimum number of days required to produce at least K eggs. You can safely assume that eggs neither gets damaged nor converted into hens.

Input

The first line consists of integers t, the number of test cases. For each test case, the first line consists two integers n and K. The next line consists of n integers representing the initial egg hatching ability of the hens.

Output

For each test case, find the minimum number of days required to produce at least K eggs.

Constraints

1 <= t <= 10^2
1 <= n <= 10^3
1 <= K <= 10^8
1 <= D[i] <= 10^8

Example

Sample Input:
3
1 4
1
2 5
2 5
5 1000000
1 2 3 4 5
Sample Output:
10
11
20000500003

Explanation of Test case #2

There are 2 hens and we need to produce 5 eggs

At time 2, Hen 0 lays an egg.

At time 5, Hen 0 and Hen1 lay an egg each.

At time 9, Hen 0 lays an egg

At time 11, Hen1 lays an egg.