```go
package main

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

const INF = 1000000000

type Node struct {
	minVal int
	maxIdx int
	lazy   int
}

var tree []Node

func build(v, tl, tr int) {
	tree[v].lazy = 0
	tree[v].minVal = INF
	tree[v].maxIdx = -1
	if tl != tr {
		tm := (tl + tr) / 2
		build(2*v, tl, tm)
		build(2*v+1, tm+1, tr)
	}
}

func push(v int) {
	if tree[v].lazy != 0 {
		tree[2*v].minVal += tree[v].lazy
		tree[2*v].lazy += tree[v].lazy
		tree[2*v+1].minVal += tree[v].lazy
		tree[2*v+1].lazy += tree[v].lazy
		tree[v].lazy = 0
	}
}

func update(v, tl, tr, l, r, add int) {
	if l > r {
		return
	}
	if l == tl && r == tr {
		tree[v].minVal += add
		tree[v].lazy += add
	} else {
		push(v)
		tm := (tl + tr) / 2
		update(2*v, tl, tm, l, min(r, tm), add)
		update(2*v+1, tm+1, tr, max(l, tm+1), r, add)
		
		if tree[2*v+1].minVal <= tree[2*v].minVal {
			tree[v].minVal = tree[2*v+1].minVal
			tree[v].maxIdx = tree[2*v+1].maxIdx
		} else {
			tree[v].minVal = tree[2*v].minVal
			tree[v].maxIdx = tree[2*v].maxIdx
		}
	}
}

func setLeaf(v, tl, tr, pos, val int) {
	if tl == tr {
		tree[v].minVal = val
		tree[v].maxIdx = pos
		tree[v].lazy = 0
	} else {
		push(v)
		tm := (tl + tr) / 2
		if pos <= tm {
			setLeaf(2*v, tl, tm, pos, val)
		} else {
			setLeaf(2*v+1, tm+1, tr, pos, val)
		}
		
		if tree[2*v+1].minVal <= tree[2*v].minVal {
			tree[v].minVal = tree[2*v+1].minVal
			tree[v].maxIdx = tree[2*v+1].maxIdx
		} else {
			tree[v].minVal = tree[2*v].minVal
			tree[v].maxIdx = tree[2*v].maxIdx
		}
	}
}

func query(v, tl, tr, l, r int) (int, int) {
	if l > r {
		return INF, -1
	}
	if l == tl && r == tr {
		return tree[v].minVal, tree[v].maxIdx
	}
	push(v)
	tm := (tl + tr) / 2
	m1, i1 := query(2*v, tl, tm, l, min(r, tm))
	m2, i2 := query(2*v+1, tm+1, tr, max(l, tm+1), r)
	
	if m2 <= m1 {
		return m2, i2
	}
	return m1, i1
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func solve() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	fmt.Fscan(reader, &t)

	for t > 0 {
		t--
		var n int
		fmt.Fscan(reader, &n)
		a := make([]int, n+1)
		for i := 1; i <= n; i++ {
			fmt.Fscan(reader, &a[i])
		}

		if len(tree) < 4*(n+1) {
			tree = make([]Node, 4*(n+1))
		}
		build(1, 1, n)

		prev := make([]int, n+1)
		lastPos := make([]int, n+1)
		dp := make([]int, n+1)
		deque := make([]int, 0, n+1)
		deque = append(deque, 0)
		dp[0] = 0
		limit := 0

		for i := 1; i <= n; i++ {
			val := a[i]
			p1 := lastPos[val]
			prev[i] = p1
			lastPos[val] = i
			p2 := 0
			if p1 > 0 {
				p2 = prev[p1]
			}

			setLeaf(1, 1, n, i, 0)
			update(1, 1, n, p1+1, i, 1)
			if p1 > 0 {
				update(1, 1, n, p2+1, p1, -1)
			}

			mn, idx := query(1, 1, n, 1, i)
			if mn == 0 {
				if idx > limit {
					limit = idx
				}
			}

			currVal := dp[i-1]
			for len(deque) > 0 && dp[deque[len(deque)-1]] >= currVal {
				deque = deque[:len(deque)-1]
			}
			deque = append(deque, i-1)

			for len(deque) > 0 && deque[0] < limit-1 {
				deque = deque[1:]
			}

			if len(deque) > 0 {
				dp[i] = dp[deque[0]] + 1
			} else {
				dp[i] = INF
			}
		}

		ans := INF
		for j := limit; j <= n; j++ {
			if dp[j] < ans {
				ans = dp[j]
			}
		}
		fmt.Fprintln(writer, ans)
	}
}

func main() {
	solve()
}
```