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.

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.

Sea, You & copriMe

Examples