```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

type Vertex struct {
	id  int
	row bool
}

type Edge struct {
	r, c  int
	color int
}

type Cycle struct {
	verts  []Vertex
	colors []int
}

func key(r, c int) int64 {
	return int64(r)<<32 | int64(c)
}

func rotateCycle(c Cycle, shift int) Cycle {
	if shift == 0 {
		return c
	}
	n := len(c.verts)
	nv := make([]Vertex, n)
	nc := make([]int, n)
	for i := 0; i < n; i++ {
		nv[i] = c.verts[(shift+i)%n]
		nc[i] = c.colors[(shift+i)%n]
	}
	return Cycle{verts: nv, colors: nc}
}

func splitCycle(c Cycle, j, color int) (Cycle, Cycle) {
	n := len(c.verts)

	v1 := append([]Vertex(nil), c.verts[:j+1]...)
	c1 := append([]int(nil), c.colors[:j]...)
	c1 = append(c1, color)

	v2 := make([]Vertex, 0, n-j+1)
	c2 := make([]int, 0, n-j+1)

	v2 = append(v2, c.verts[0])
	for i := n - 1; i >= j; i-- {
		v2 = append(v2, c.verts[i])
	}

	c2 = append(c2, c.colors[n-1])
	for i := n - 1; i > j; i-- {
		c2 = append(c2, c.colors[i-1])
	}
	c2 = append(c2, color)

	return Cycle{verts: v1, colors: c1}, Cycle{verts: v2, colors: c2}
}

func chooseRainbow(c Cycle, a, b Cycle, j, color int) Cycle {
	matchA := false
	for i := 0; i < j; i++ {
		if c.colors[i] == color {
			matchA = true
			break
		}
	}
	matchB := false
	for i := j; i < len(c.colors); i++ {
		if c.colors[i] == color {
			matchB = true
			break
		}
	}
	if !matchA && !matchB {
		if len(a.verts) <= len(b.verts) {
			return a
		}
		return b
	}
	if !matchA {
		return a
	}
	return b
}

func searchChord(c Cycle, edges []Edge) (bool, int, int, int) {
	rowPos := make(map[int]int)
	colPos := make(map[int]int)
	for i, v := range c.verts {
		if v.row {
			rowPos[v.id] = i
		} else {
			colPos[v.id] = i
		}
	}
	n := len(c.verts)
	for _, e := range edges {
		pr, okr := rowPos[e.r]
		pc, okc := colPos[e.c]
		if !okr || !okc {
			continue
		}
		if (pr+1)%n == pc || (pc+1)%n == pr {
			continue
		}
		j := (pc - pr + n) % n
		if j <= 0 || j >= n || j%2 == 0 {
			continue
		}
		return true, pr, j, e.color
	}
	return false, 0, 0, 0
}

func findInitialCycle(n int, adj [][]int, colors map[int64]int) Cycle {
	total := 2 * n
	parent := make([]int, total)
	state := make([]int, total)
	for i := 0; i < total; i++ {
		parent[i] = -1
	}

	var cyc []int
	var dfs func(int) bool
	dfs = func(u int) bool {
		state[u] = 1
		for _, v := range adj[u] {
			if v == parent[u] {
				continue
			}
			if state[v] == 0 {
				parent[v] = u
				if dfs(v) {
					return true
				}
			} else if state[v] == 1 {
				path := []int{u}
				x := u
				for x != v {
					x = parent[x]
					path = append(path, x)
				}
				for l, r := 0, len(path)-1; l < r; l, r = l+1, r-1 {
					path[l], path[r] = path[r], path[l]
				}
				cyc = path
				return true
			}
		}
		state[u] = 2
		return false
	}

	for i := 0; i < total && cyc == nil; i++ {
		if state[i] == 0 {
			if dfs(i) {
				break
			}
		}
	}

	if cyc[0] >= n {
		cyc = append(cyc[1:], cyc[0])
	}

	m := len(cyc)
	verts := make([]Vertex, m)
	ecol := make([]int, m)

	for i, x := range cyc {
		if x < n {
			verts[i] = Vertex{id: x + 1, row: true}
		} else {
			verts[i] = Vertex{id: x - n + 1, row: false}
		}
	}

	for i := 0; i < m; i++ {
		a := cyc[i]
		b := cyc[(i+1)%m]
		var r, c int
		if a < n {
			r = a + 1
			c = b - n + 1
		} else {
			r = b + 1
			c = a - n + 1
		}
		ecol[i] = colors[key(r, c)]
	}

	return Cycle{verts: verts, colors: ecol}
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	if _, err := fmt.Fscan(in, &t); err != nil {
		return
	}

	for ; t > 0; t-- {
		var n int
		if _, err := fmt.Fscan(in, &n); err != nil {
			return
		}

		colors := make(map[int64]int, 2*n+20)
		edges := make([]Edge, 0, 2*n+10)
		adj := make([][]int, 2*n)

		for color := 1; color <= 2*n; color++ {
			var x, y int
			fmt.Fscan(in, &x, &y)
			colors[key(x, y)] = color
			edges = append(edges, Edge{r: x, c: y, color: color})
			r := x - 1
			c := n + y - 1
			adj[r] = append(adj[r], c)
			adj[c] = append(adj[c], r)
		}

		cyc := findInitialCycle(n, adj, colors)
		queries := 0

		for len(cyc.verts) > 4 {
			for {
				found, shift, j, color := searchChord(cyc, edges)
				if !found {
					break
				}
				cyc = rotateCycle(cyc, shift)
				a, b := splitCycle(cyc, j, color)
				cyc = chooseRainbow(cyc, a, b, j, color)
				if len(cyc.verts) <= 4 {
					break
				}
			}

			if len(cyc.verts) <= 4 {
				break
			}

			L := len(cyc.verts)
			j := L / 2
			if j%2 == 0 {
				j--
			}
			if j < 3 {
				j = 3
			}
			if j > L-3 {
				j = L - 3
				if j%2 == 0 {
					j--
				}
			}

			r := cyc.verts[0].id
			c := cyc.verts[j].id

			fmt.Fprintln(out, "?", r, c)
			out.Flush()

			var color int
			if _, err := fmt.Fscan(in, &color); err != nil {
				return
			}
			if color == -1 {
				return
			}

			queries++
			edges = append(edges, Edge{r: r, c: c, color: color})
			a, b := splitCycle(cyc, j, color)
			cyc = chooseRainbow(cyc, a, b, j, color)

			if queries > 10 {
				return
			}
		}

		r1 := cyc.verts[0].id
		c1 := cyc.verts[1].id
		r2 := cyc.verts[2].id
		c2 := cyc.verts[3].id

		fmt.Fprintln(out, "!", r1, c1, r2, c1, r2, c2, r1, c2)
		out.Flush()
	}
}
```