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

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

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

and so on.

Given n - the number of hens and the array D - the initial egg laying 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 Hen 1 lay an egg each.

At time 9, Hen 0 lays an egg

At time 11, Hen 1 lays an egg.