题目描述

Vladislav 有一个包含 $n$ 首歌曲的播放列表，歌曲编号为 $1$ 到 $n$。第 $i$ 首歌有流派 $g_i$ 和作者 $w_i$。

若播放列表中任意两首相邻歌曲满足下列至少一项：作者相同，或流派相同，则称这个播放列表为精彩的。$g_i,w_i$ 都是长度不超过 $10^4$ 的字符串。

不一定能让所有歌曲组成精彩播放列表，因此允许进行如下两步操作：

1. 删除任意数量（可以为 $0$）的歌曲；
2. 任意重排剩余歌曲。

请问最少删除多少首歌曲，才能使剩余歌曲能够排列成一个精彩播放列表。

输入格式

第一行一个整数 $t$（$1\le t\le1000$），表示测试组数。

对每组数据：

• 第一行一个整数 $n$（$1\le n\le16$），表示初始播放列表中的歌曲数；
• 接下来 $n$ 行，第 $i$ 行包含两个只由小写英文字母组成的字符串 $g_i,w_i$（$1\le|g_i|,|w_i|\le10^4$），分别表示第 $i$ 首歌的流派与作者。

保证所有测试组的 $2^n$ 之和不超过 $2^{16}$，且所有字符串长度 $|g_i|+|w_i|$ 的总和不超过 $4\cdot10^5$。

输出格式

对每组数据输出一个整数，表示使播放列表能够变得精彩所需删除歌曲数的最小值。

样例

样例 1

输入：

4
1
pop taylorswift
4
electronic themotans
electronic carlasdreams
pop themotans
pop irinarimes
7
rap eminem
rap drdre
rap kanyewest
pop taylorswift
indierock arcticmonkeys
indierock arcticmonkeys
punkrock theoffspring
4
a b
c d
e f
g h

输出：

0
0
4
3