Doremy 有 $n$ 桶油漆，用一个长度为 $n$ 的数组 $a$ 表示。第 $i$ 桶油漆的颜色为 $a_i$。

设 $c(l, r)$ 为子数组 $[a_l, a_{l+1}, \dots, a_r]$ 中不同元素的个数。请选择两个整数 $l$ 和 $r$，满足 $l \le r$，使得 $r - l - c(l, r)$ 的值最大。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$) — 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出 $l$ 和 $r$，使得 $l \le r$ 且 $r - l - c(l, r)$ 最大。

如果存在多个解，你可以输出其中任意一个。

样例

输入样例 1

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

输出样例 1

2 4
1 5
1 4
2 3
1 2
1 1
3 9

说明

在第一个测试用例中，$a = [1, 3, 2, 2, 4]$。

• 当 $l = 1$ 且 $r = 3$ 时，$c(l, r) = 3$（在 $[1, 3, 2]$ 中有 $3$ 个不同的元素）。
• 当 $l = 2$ 且 $r = 4$ 时，$c(l, r) = 2$（在 $[3, 2, 2]$ 中有 $2$ 个不同的元素）。

可以证明，选择 $l = 2$ 且 $r = 4$ 可以使 $r - l - c(l, r)$ 的值最大，最大值为 $0$。

对于第二个测试用例，$a = [1, 2, 3, 4, 5]$。

• 当 $l = 1$ 且 $r = 5$ 时，$c(l, r) = 5$（在 $[1, 2, 3, 4, 5]$ 中有 $5$ 个不同的元素）。
• 当 $l = 3$ 且 $r = 3$ 时，$c(l, r) = 1$（在 $[3]$ 中有 $1$ 个不同的元素）。

可以证明，选择 $l = 1$ 且 $r = 5$ 可以使 $r - l - c(l, r)$ 的值最大，最大值为 $-1$。选择 $l = 3$ 且 $r = 3$ 也是可以接受的。