Vladislav 的播放列表由 $$$n$$$ 歌曲组成,编号从 $$$1$$$ 到 $$$n$$$。歌曲 $$$i$$$ 的流派为 $$$g_i$$$,作者为 $$$w_i$$$。他希望制作一个播放列表,使得每对相邻的歌曲要么具有相同的作者,要么来自相同的流派(或两者)。他称这样的播放列表令人兴奋。 $$$g_i$$$ 和 $$$w_i$$$ 都是长度不超过 $$$10^4$$$ 的字符串。
可能并不总是能够使用所有歌曲制作令人兴奋的播放列表,因此随机播放过程分两步进行。首先,删除一定数量(可能为零)的歌曲,然后重新排列播放列表中的剩余歌曲以使其令人兴奋。
由于 Vladislav 不喜欢歌曲从他的播放列表中删除,因此他希望制作播放列表执行尽可能少的删除操作。帮助他找到需要执行的最少删除次数,以便能够重新排列其余歌曲,使播放列表变得令人兴奋。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 16$$$) — 原始播放列表中的歌曲数量。
接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含两串小写字母 $$$g_i$$$ 和 $$$w_i$$$ ($$$1 \leq |g_i|, |w_i| \leq 10^4$$$) — 第 $$$i$$$ 歌曲的流派和作者。其中 $$$|g_i|$$$ 和 $$$|w_i|$$$ 是字符串的长度。
所有测试用例的 $$$2^n$$$ 总和不超过 $$$2^{16}$$$。
$$$|g_i| 的总和+ |w_i|$$$ 所有测试用例不超过 $$$4 \cdot 10^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
输出 #1
0 0 4 3
注意
在第一个测试用例中,播放列表已经令人兴奋。
在第二个测试用例中,如果您的歌曲顺序为 $$$4, 3, 1, 2$$$,那就很令人兴奋,因此您不需要删除任何歌曲。
在第三个测试用例中,您可以删除歌曲 $$$4, 5, 6, 7$$$。然后播放列表中的歌曲顺序为 $$$1, 2, 3$$$ 令人兴奋。