package main

import (
	"bufio"
	"os"
	"sort"
	"strconv"
)

var scanner *bufio.Scanner
var out *bufio.Writer

func readInt() int {
	scanner.Scan()
	v, _ := strconv.Atoi(scanner.Text())
	return v
}

const INF = 1e9

type Edge struct {
	to  int
	cap int
	rev int
}

var graph [][]Edge
var level []int
var ptr []int
var q []int

func initDinic(n int) {
	if len(graph) < n {
		graph = make([][]Edge, n)
		level = make([]int, n)
		ptr = make([]int, n)
		q = make([]int, n)
	}
	for i := 0; i < n; i++ {
		graph[i] = graph[i][:0]
	}
}

func addEdge(from, to, cap int) {
	graph[from] = append(graph[from], Edge{to, cap, len(graph[to])})
	graph[to] = append(graph[to], Edge{from, 0, len(graph[from]) - 1})
}

func bfs(s, t, n int) bool {
	for i := 0; i < n; i++ {
		level[i] = -1
	}
	level[s] = 0
	head, tail := 0, 0
	q[tail] = s
	tail++
	for head < tail {
		v := q[head]
		head++
		for _, edge := range graph[v] {
			if edge.cap > 0 && level[edge.to] == -1 {
				level[edge.to] = level[v] + 1
				q[tail] = edge.to
				tail++
			}
		}
	}
	return level[t] != -1
}

func dfs(v, t, pushed int) int {
	if pushed == 0 || v == t {
		return pushed
	}
	for ptr[v] < len(graph[v]) {
		edge := &graph[v][ptr[v]]
		tr := edge.to
		if level[v]+1 != level[tr] || edge.cap == 0 {
			ptr[v]++
			continue
		}
		push := pushed
		if edge.cap < push {
			push = edge.cap
		}
		pushedFlow := dfs(tr, t, push)
		if pushedFlow == 0 {
			ptr[v]++
			continue
		}
		edge.cap -= pushedFlow
		graph[tr][edge.rev].cap += pushedFlow
		return pushedFlow
	}
	return 0
}

func maxFlow(s, t, n int) int {
	flow := 0
	for bfs(s, t, n) {
		for i := 0; i < n; i++ {
			ptr[i] = 0
		}
		for {
			pushed := dfs(s, t, INF)
			if pushed == 0 {
				break
			}
			flow += pushed
		}
	}
	return flow
}

var Occ [][]int
var vals []int
var Ul, Ur []int
var z int

func check(m int) bool {
	if m == 0 {
		return true
	}
	if 2*m > z {
		return false
	}

	F := 0
	Ul = Ul[:0]
	Ur = Ur[:0]

	for _, v := range vals {
		arr := Occ[v]
		idx := sort.Search(len(arr), func(i int) bool { return arr[i] >= m })

		if idx < len(arr) && arr[idx] <= z-m {
			F++
		} else {
			lv := 0
			if idx > 0 {
				lv = arr[idx-1]
			}
			rv := 0
			if idx < len(arr) {
				rv = z - arr[idx]
			}
			if lv > 0 || rv > 0 {
				Ul = append(Ul, lv)
				Ur = append(Ur, rv)
			}
		}
	}

	if F >= m {
		return true
	}

	k := m - F
	if k > len(Ul) {
		return false
	}

	nodes := 2*m + len(Ul)
	initDinic(nodes)
	S := 0
	T := 1

	for x := 1; x < m; x++ {
		addEdge(x+1, T, 1)
		if x > 1 {
			addEdge(x+1, x, INF)
		}
	}
	for y := 1; y < m; y++ {
		addEdge(m+y, T, 1)
		if y > 1 {
			addEdge(m+y, m+y-1, INF)
		}
	}

	for i := 0; i < len(Ul); i++ {
		vNode := 2*m + i
		addEdge(S, vNode, 1)
		if Ul[i] > 0 {
			addEdge(vNode, Ul[i]+1, 1)
		}
		if Ur[i] > 0 {
			addEdge(vNode, m+Ur[i], 1)
		}
	}

	flow := maxFlow(S, T, nodes)
	return flow >= k
}

func solve() {
	n := readInt()
	if len(Occ) < n+1 {
		newOcc := make([][]int, n+1)
		copy(newOcc, Occ)
		Occ = newOcc
	}
	for i := 0; i <= n; i++ {
		Occ[i] = Occ[i][:0]
	}

	z = 0
	for i := 0; i < n; i++ {
		v := readInt()
		if v == 0 {
			z++
		} else {
			Occ[v] = append(Occ[v], z)
		}
	}

	vals = vals[:0]
	for i := 1; i <= n; i++ {
		if len(Occ[i]) > 0 {
			vals = append(vals, i)
		}
	}

	low, high := 0, z/2
	ans := 0
	for low <= high {
		mid := (low + high) / 2
		if check(mid) {
			ans = mid
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	out.WriteString(strconv.Itoa(ans) + "\n")
}

func main() {
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024*1024), 1024*1024*10)
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()

	if !scanner.Scan() {
		return
	}
	t, _ := strconv.Atoi(scanner.Text())

	for i := 0; i < t; i++ {
		solve()
	}
}