H. Sea, You & copriMe
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Umi is given an array $$$a$$$ of length $$$n$$$, whose elements are integers between $$$1$$$ and $$$m$$$. She loves coprime integers and wants to find four distinct indices $$$p, q, r, s$$$ ($$$1 \le p, q, r, s \le n$$$), such that $$$\gcd(a_p, a_q) = 1$$$ and $$$\gcd(a_r, a_s) = 1$$$$$$^{\text{∗}}$$$.

If there are multiple solutions, you may output any one of them.

$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$4 \le n \le 2 \cdot 10^5, 1 \le m \le 10^6$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le m$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and that the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case:

  • If no such set of four distinct indices exists, output one integer $$$0$$$.
  • Otherwise, output four distinct integers $$$p, q, r, s$$$ ($$$1 \le p, q, r, s \le n$$$) that satisfy the condition. If there are multiple solutions, output any one of them.
Example
Input
5
4 15
4 7 9 15
4 10
1 2 4 8
5 15
6 10 11 12 15
5 15
6 10 11 14 15
6 10000
30 238 627 1001 1495 7429
Output
1 3 2 4
0
0
3 1 4 5
1 4 2 3
Note

In the first test case, $$$\gcd(a_1, a_3) = \gcd(4, 9) = 1$$$, $$$\gcd(a_2, a_4) = \gcd(7, 15) = 1$$$.

In the second test case, it can be shown that no such quadruple exists.