该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

吉吉国王有一个包含 $n$ 首歌的歌单，歌编号从 $1$ 到 $n$。第 $i$ 首歌的风格为 $g_i$，作者为 $w_i$。

他想制作一个歌单，使得每对相邻歌要么有相同的作者，要么属于相同的风格（或两者都满足）。$g_i$ 和 $w_i$ 都是长度不超过 $10^4$ 的字符串。

有时可能无法使用所有歌制作出满足吉吉国王需求的歌单，因此洗牌过程分为两步：首先，删掉一定数量的歌（可能为零），然后重新排列剩余的歌，使其成为满足要求的歌单。

由于吉吉国王不喜欢自己的歌被删掉，他希望制作歌单时删除的歌曲数量尽可能少。请帮助他找到需要移除的最少歌曲数量，以便能将剩余的歌重新排列成满足他需求的歌单。

输入格式

第一行输入一个整数 $t$（$1 \leq t \leq 1000$）—— 测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 16$）—— 原始歌单中的歌曲数量。

然后是 $n$ 行，第 $i$ 行包含两个由小写字母组成的字符串 $g_i$ 和 $w_i$（$1 \leq |g_i|, |w_i| \leq 10^4$）—— 第 $i$ 首歌曲的风格和作者。其中 $|g_i|$ 和 $|w_i|$ 分别是字符串 $g_i$ 和 $w_i$ 的长度。

输出格式

对于每个测试用例，输出一个整数——为使结果歌曲可被制作成满足吉吉国王要求的歌单，需要删除的最少歌曲数量。

样例

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

样例解释

• 第一组样例的歌单已经满足要求
• 第二组样例，无需删除，只需选择 $4,3,1,2$ 可满足要求
• 第三组样例，删除 $4,5,6,7$，选择 $1,2,3$ 可满足要求