Go Back
Lecture Bunk (200)
Description

Barath and Mithil have decided to bunk lectures but they always attend first lecture, and when there is only one lecture, basically they can’t bunk. There are ‘p’ no. of lectures happening in college
and ‘s’ is the time required between two consecutive lectures to bunk the class. Ti is the time delay, with respect to decided schedule, by teacher to reach the class
and ‘i’ is the lecture number. Now each teacher extends the lecture by time Ti, again with respect to schedule. Now next teacher, if arrived before the previous one left, will wait outside the class till this lecture gets done, and then enter as soon as the previous teacher leaves.

Input

The first line of input contain an integer ‘T’ denoting the number of test cases. Each test case consists of two line. First line consists of two space separated integers, ‘p’ and ‘s’, where ‘p’ is number of lectures and ‘s’ is time required to bunk. Next line has ‘p’ space separated integers, ‘Ti’ indicating ith teacher’s time delay.

Output

For each test case, print a new line consisting of an integer, which is the lecture number just before which they are able to escape the lecture.If they cannot bunk, print -1.

Constraints

1<=t<=100
1<=p<=20
1<=q<=20
1<=Ti<=20

Example
Copy Input

Input:
1
5 3
1 3 7 8 5
Output:
3

Explanation

For first lecture teacher came one minute late so he extended by 1 minute. Next teacher entered the class 3 minutes with respect to schedule, so we only got 2 minutes in between (3-1). Next we get 4 minutes and we are able to bunk just before 3rd lecture. Hence print 3.

Single Round Match #08
3 hour contest



Announcement

Problem Tags
adhoc, math

Supported by our Coding Partner