M. Prime Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a sequence of prime numbers $$$p_1, p_2, \dots, p_n$$$, where each $$$p_i$$$ is a prime number no greater than $$$10^7$$$.

Find two intervals $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ that satisfy $$$1 \le l_1 \le r_1 \le n$$$, $$$1 \le l_2 \le r_2 \le n$$$ and $$$(l_1, r_1) \neq (l_2, r_2)$$$, such that the product of all elements inside the two intervals is equal:

$$$$$$ \prod_{i=l_1}^{r_1} p_i = \prod_{j=l_2}^{r_2} p_j $$$$$$

You may output any valid pair if multiple solutions exist. If no such pair of distinct intervals exists, output -1.

Input

The first line contains a positive integer $$$T$$$ $$$(1 \le T \le 10^5)$$$, denoting the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ $$$(2 \le n \le 2 \times 10^5)$$$, representing the length of the sequence.
  • The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$. Each $$$p_i$$$ is a prime number not exceeding $$$10^7$$$.

Guarantee: The sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case:

  • If a valid solution exists, output four integers $$$l_1, r_1, l_2, r_2$$$ on a single line, which are the left and right endpoints of the two intervals. You can arrange the two intervals in any order, and $$$l_1 \le r_1$$$, $$$l_2 \le r_2$$$ must hold.
  • If no valid solution exists, output -1 on a single line.
Example
Input
3
4
2 2 2 2
5
2 3 5 7 11
7
17 2 5 17 5 5 2
Output
1 3 2 4
-1
2 5 4 7
Note

There are three test cases in the sample.

For the first test case, select $$$l_1 = 1, r_1 = 3, l_2 = 2, r_2 = 4$$$. We have $$$\prod_{i=l_1}^{r_1} p_i = \prod_{j=l_2}^{r_2} p_j = 8$$$.

For the second test case, it can be proven that there is no valid solution.

For the third test case, select $$$l_1 = 2, r_1 = 5, l_2 = 4, r_2 = 7$$$. We have $$$\prod_{i=l_1}^{r_1} p_i = \prod_{j=l_2}^{r_2} p_j = 850$$$.