Go Back
Predict Shambhavi (200)
Description

It is the time of Cognition and Shambhavi has participated in N events numbered from 1 to N. Each of these events have a particular waiting time ( in minutes ), W(i) ( 1 <= i <= N ) for which Shambhavi has to wait for her turn in that event. However, Shambhavi doesn’t like to wait at a particular place. So she keeps moving from one event location to another, until her turn arrives.

Shambhavi starts visiting the events from the 1st event.
If Shambhavi is at the location of the ith ( 1 <= i <= N-1 ) event AND W(i) > 0, She will leave instantly and move to the next ( (i+1)th ) event location.
In case if i=N, she will move back to the 1st event location.
In case if Shambhavi is at the ith event location and W(i) = 0 , she will take her turn in that event. ( Here, W(i) = 0 indicates that the waiting time is over ).
The time taken by Shambhavi to move from any event location to another is exactly 1 minute.

Predict the first event in which Shambhavi will enter.

Input

The first line of the input consists of a single integer T, denoting the number of Test Cases.
The description of T test cases follow :
The first line of each test case consists of a single integer N.
The second line of each test cases consists of N space-separated integers W(i).

Output

For each test case, output a single line consisting of a single integer, the number of the first event in which Shambhavi will enter.

Constraints

1 <= T <= 100
1 <= N <= 10^5
0 <= W(i) <= 10^9

Example
Copy Input

Input:
2
4
4 2 1 3
6
7 5 3 4 5 7

Output:
3
2

Explanation

Test Case 1 :
Initial timings -> 4 2 1 3
After Shambhavi moves from 1 to 2 -> 3 1 0 2
After Shambhavi moves from 2 to 3 -> 2 0 0 1
Here as W(i) = 0, Shambhavi enters the 3rd event first.

Single Round Match #03
3 hour contest



Announcement
First 4 submissions made at the start are rejudged :)

Problem Tags
dp,math

Supported by our Coding Partner