```go
package main

import (
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const MAXM = 1000005

var spf [MAXM]int
var cnt [MAXM]int
var gen [MAXM]int
var current_gen int

func initSPF() {
	for i := 2; i < MAXM; i++ {
		spf[i] = i
	}
	for i := 2; i*i < MAXM; i++ {
		if spf[i] == i {
			for j := i * i; j < MAXM; j += i {
				if spf[j] == j {
					spf[j] = i
				}
			}
		}
	}
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

type Div struct {
	d  int
	mu int
}

var data []byte
var ptr int

func readInt() int {
	for ptr < len(data) && (data[ptr] < '0' || data[ptr] > '9') {
		ptr++
	}
	if ptr >= len(data) {
		return 0
	}
	res := 0
	for ptr < len(data) && data[ptr] >= '0' && data[ptr] <= '9' {
		res = res*10 + int(data[ptr]-'0')
		ptr++
	}
	return res
}

func main() {
	initSPF()

	data, _ = io.ReadAll(os.Stdin)
	t := readInt()

	var a []int
	var primes []int
	var divs [128]Div

	var out strings.Builder

	for tc := 0; tc < t; tc++ {
		n := readInt()
		m := readInt()
		_ = m

		if len(a) < n+1 {
			a = make([]int, n+1)
		}
		for i := 1; i <= n; i++ {
			a[i] = readInt()
		}

		find_edge := func(exclude_p, exclude_q int) (int, int) {
			current_gen++
			for i := 1; i <= n; i++ {
				if i == exclude_p || i == exclude_q {
					continue
				}
				val := a[i]
				primes = primes[:0]
				temp := val
				for temp > 1 {
					p := spf[temp]
					primes = append(primes, p)
					for temp%p == 0 {
						temp /= p
					}
				}

				num_divs := 1 << len(primes)
				divs[0] = Div{1, 1}
				for k := 0; k < len(primes); k++ {
					half := 1 << k
					p := primes[k]
					for j := 0; j < half; j++ {
						divs[half+j] = Div{divs[j].d * p, -divs[j].mu}
					}
				}

				coprime_count := 0
				for j := 0; j < num_divs; j++ {
					d := divs[j].d
					if gen[d] != current_gen {
						cnt[d] = 0
						gen[d] = current_gen
					}
					if divs[j].mu == 1 {
						coprime_count += cnt[d]
					} else {
						coprime_count -= cnt[d]
					}
				}

				if coprime_count > 0 {
					for j := 1; j < i; j++ {
						if j == exclude_p || j == exclude_q {
							continue
						}
						if gcd(a[j], val) == 1 {
							return j, i
						}
					}
				}

				for j := 0; j < num_divs; j++ {
					cnt[divs[j].d]++
				}
			}
			return 0, 0
		}

		p, q := find_edge(0, 0)
		if p == 0 {
			out.WriteString("0\n")
			continue
		}

		r, s := find_edge(p, q)
		if r != 0 {
			out.WriteString(strconv.Itoa(p) + " " + strconv.Itoa(q) + " " + strconv.Itoa(r) + " " + strconv.Itoa(s) + "\n")
			continue
		}

		var adj_p, adj_q [2]int
		p_len, q_len := 0, 0

		for i := 1; i <= n; i++ {
			if i == p || i == q {
				continue
			}
			if p_len < 2 && gcd(a[i], a[p]) == 1 {
				adj_p[p_len] = i
				p_len++
			}
			if q_len < 2 && gcd(a[i], a[q]) == 1 {
				adj_q[q_len] = i
				q_len++
			}
		}

		found := false
		var ans_a, ans_b int
		for i := 0; i < p_len; i++ {
			for j := 0; j < q_len; j++ {
				if adj_p[i] != adj_q[j] {
					ans_a = adj_p[i]
					ans_b = adj_q[j]
					found = true
					break
				}
			}
			if found {
				break
			}
		}

		if found {
			out.WriteString(strconv.Itoa(p) + " " + strconv.Itoa(ans_a) + " " + strconv.Itoa(q) + " " + strconv.Itoa(ans_b) + "\n")
		} else {
			out.WriteString("0\n")
		}
	}
	fmt.Print(out.String())
}
```