Teleporter Run

Consider the points 0, 1, ..., n+1 on a number line. There is a teleporter at each of the points 1, 2, ..., n.

While you are standing at a point i, you may do any of the following:

move one unit to the left, costing 1 coin;
move one unit to the right, costing 1 coin;
if 1 <= i <= n and the teleporter at point i has not been used yet, use it, costing a[i] coins. When you use it you choose where it sends you: either point 0 or point n+1.

Once a teleporter has been used it is gone and can never be used again.

You start at point 0 holding c coins, and you may never spend more coins than you have.

Find the maximum number of teleporters you can use.

Input Format

The first line contains a single integer t, the number of test cases.

Each test case is given on two lines:

the first line contains two integers n and c, the number of teleporters and the number of coins you start with;
the second line contains n integers a[1], a[2], ..., a[n], where a[i] is the price of the teleporter at point i.

Output Format

For each test case, print a single line containing the maximum number of teleporters you can use.

Constraints

1 <= t <= 1000
1 <= n
1 <= c <= 10^9
1 <= a[i] <= 10^9
The sum of n over all test cases does not exceed 15000.

Example 1

Input

10
5 6
1 1 1 1 1
8 32
100 52 13 6 9 4 100 35
1 1
5
4 5
4 3 2 1
5 9
2 3 1 4 1
5 8
2 3 1 4 1
4 3
2 3 4 1
4 9
5 4 3 3
2 14
7 5
5 600000000
500000000 400000000 300000000 200000000 100000000

Output

Explanation

In the first test case you have 6 coins and every teleporter costs 1.

Move right once, from point 0 to point 1: 1 coin spent, 5 left.
Use the teleporter at point 1 and choose to be sent to point 6: 1 more coin spent, 4 left.
Move left once, from point 6 to point 5: 1 more coin spent, 3 left.
Use the teleporter at point 5: 1 more coin spent, 2 left.

That is 2 teleporters for 4 coins. The two remaining coins are not enough to walk to any surviving teleporter and pay for it, so 2 is the maximum.

In the third test case the only teleporter costs 5, and simply reaching it already costs 1, so with 1 coin you can use nothing at all.

Example 2

Input

4
6 7
9 9 9 9 9 1
6 8
9 9 9 9 9 1
6 12
9 9 9 9 9 1
6 3
1 9 9 9 9 9

Output

Explanation

In the first three test cases the cheap teleporter sits at point 6, far from your starting point. Reaching it from point 0 costs 6 coins on top of its price of 1, so starting there always costs 7.

With 7 or 8 coins that is all you can afford: one teleporter.

With 12 coins it pays to start elsewhere. Walk to point 1 and use its teleporter for 1 + 9 = 10 coins, choosing to be sent to point 7. From point 7 the teleporter at point 6 is one step away, so it costs only 1 + 1 = 2 more. Two teleporters for 12 coins exactly.