```go
package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	
	var t int
	fmt.Fscan(in, &t)
	
	for tc := 0; tc < t; tc++ {
		var n int
		fmt.Fscan(in, &n)
		
		g := make([]string, n)
		w := make([]string, n)
		for i := 0; i < n; i++ {
			fmt.Fscan(in, &g[i], &w[i])
		}
		
		compat := make([][]bool, n)
		for i := 0; i < n; i++ {
			compat[i] = make([]bool, n)
			for j := 0; j < n; j++ {
				compat[i][j] = (g[i] == g[j]) || (w[i] == w[j])
			}
		}
		
		size := 1 << n
		dp := make([][]bool, size)
		for i := range dp {
			dp[i] = make([]bool, n)
		}
		
		for i := 0; i < n; i++ {
			dp[1<<i][i] = true
		}
		
		maxKeep := 0
		for mask := 0; mask < size; mask++ {
			cnt := bits.OnesCount(uint(mask))
			if cnt > maxKeep {
				for i := 0; i < n; i++ {
					if dp[mask][i] {
						maxKeep = cnt
						break
					}
				}
			}
			
			for last := 0; last < n; last++ {
				if !dp[mask][last] {
					continue
				}
				for nxt := 0; nxt < n; nxt++ {
					if mask&(1<<nxt) != 0 {
						continue
					}
					if !compat[last][nxt] {
						continue
					}
					dp[mask|1<<nxt][nxt] = true
				}
			}
		}
		
		fmt.Fprintln(out, n-maxKeep)
	}
}
```