Doremy has n buckets of paint which is represented by an array a of length n.?

Bucket i contains paint with color ai.

Let c(l,r) be the number of distinct elements in the subarray [al,al+1,…,ar].

?Choose 2 integers l and r such that l≤r and r?l?c(l,r) is maximized.

Input

The input consists of multiple test cases. The first line contains a single integer t

?(1≤t≤104)? — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤105) — the length of the array a.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n).

It is guaranteed that the sum of n does not exceed 105.

Output

For each test case, output l and r such that l≤r and r?l?c(l,r) is maximized.

If there are multiple solutions, you may output any.

Example

input

7

5

1 3 2 2 4

5

1 2 3 4 5

4

2 1 2 1

3

2 3 3

2

2 2

1

1

9

9 8 5 2 1 1 2 3 3

output

2 4

1 5

1 4

2 3

1 2

1 1

3 9

Note

In the first test case, a=[1,3,2,2,4].

When l=1 and r=3, c(l,r)=3 (there are 3 distinct elements in [1,3,2]).

When l=2 and r=4, c(l,r)=2 (there are 2 distinct elements in [3,2,2]).

It can be shown that choosing l=2 and r=4 maximizes the value of r?l?c(l,r) at 0.

For the second test case, a=[1,2,3,4,5].

When l=1 and r=5, c(l,r)=5 (there are 5 distinct elements in [1,2,3,4,5]).

When l=3 and r=3, c(l,r)=1 (there is 1 distinct element in [3]).

It can be shown that choosing l=1 and r=5 maximizes the value of r?l?c(l,r) at ?1.?

Choosing l=3 and r=3 is also

---------------------------------

理解題意就好了，其實(shí)對于左邊的數(shù)字沒有影響的，就是如何找到右邊的數(shù)字，這里面右邊的數(shù)字必須是有重復(fù)值的最右邊的這個數(shù)字。找到即可返回。

代碼如下：