winter-is-coming-12

"Winter Is Coming". This is what they say in "Game of Thrones". This is yet another day in King's Landing and Tyrion Lannister is doing his job of "Hand of king". While looking at his ledger he finds a unique pattern with numbers. Tyrion has N numbers and he finds and there is always a sub-array(continuous subset) of numbers whose sum is divisible by N. To test his hypothesis he comes up with T(Test Cases) sets of N integers and tries to find smallest sub-array whose sum is divisible by N. If multiple answers are possible print the sub-array which occurs left most in array of integers.

Input
First line of input is T, number of test cases. Each test case has two lines. First line is N. Next line contains N integers, the array Tyrion considers to test his hypothesis.

Output
For each input Output the smallest sub-array with sum divisible by N. The index of range of sub-array to be be printed should be 1-based.

Constraints:
1 ≤ Elements of array ≤ 10^9
1 ≤ T ≤ 10
1 ≤ N ≤ 100000

Explanation:
Test Case 1: sum from index 3 to 3 is 3 divisible by 3. 
Test Case 2: sum from index 1 to 2 is 3 divisible by 3. 

SAMPLE INPUT
2
3
1 1 3
3
1 2 1SAMPLE OUTPUT
3 3
1 2

Source: hackerearth | Difficulty: MEDIUM


Solutions: