Aniruddha is given a milestone M to reach in terms of distance. He is living in a different Galaxy where there are N days in a year.At the ith day he can walk atmost X distance.Assuming he walks optimally you need to output the minimum day number on which he will reach the milestone.

Input

The first input line contains the T number of testcases. Each testcase consist of three lines First line consist of single integer N — the number of days in a year.

Next line contains N non-negative space-separated numbers— i.e. distance which Aniruddha will walk on ith day. It is guaranteed that at least one of those numbers is greater than zero.

And the third line consist of the value of milestone which Aniruddha has to reach.

Output

For each testcase you need to output the answer to the following query.

Constraints

1<=T<= 10

1<=N<=10^5

0<=X<=10^8

0<=M<=10^16