题目描述

弗拉迪斯拉夫有一个播放列表，其中包含 n 首歌曲，编号从 1 到 n。歌曲 i 的体裁为 $g_i$，作者为 $w_i$。他想制作这样一个播放列表：每对相邻的歌曲要么有相同的作者，要么来自相同的流派（或两者都相同）。他把这样的播放列表称为令人兴奋的播放列表。$g_i$ 和 $w_i$ 都是长度不超过 $10^4$ 的字符串。

要想用所有歌曲制作出令人兴奋的播放列表并不总是可能的，因此洗牌过程分两步进行。首先，移除一定数量（可能为零）的歌曲，然后重新排列播放列表中的剩余歌曲，使其更加精彩。

由于弗拉迪斯拉夫不喜欢播放列表中的歌曲被移除，因此他希望制作的播放列表能尽可能少地移除歌曲。帮助他找出需要执行的最少移除次数，以便能够重新排列剩余的歌曲，使播放列表变得精彩。

输入格式

输入的第一行包含一个整数 t ( 1≤t≤1000 ) - 测试样例的数量。每个测试样例的第一行包含一个整数 n ( 1≤n≤16 ) -- 原始播放列表中的歌曲数量。然后是 n 行，其中第 i 行包含两个小写字母字符串 $g_i$ 和 $w_i$ ( 1≤|$g_i$|,|$w_i$|≤10^4 ) -- 第 i 首歌曲的流派和作者。其中，|$g_i$| + |$w_i$| 是字符串的长度。

所有测试样例的 $2^n$ 之和不超过 $2^{16}$。

所有测试样例的 |$g_i$| + |$w_i$| 之和不超过 $4 ⋅ 10^5$。

输出格式

对于每个测试样例，输出一个整数--为使生成的播放列表令人兴奋而必须删除的最少次数。

说明/提示

在第一个测试样例中，播放列表已经很精彩了。

在第二个测试样例中，如果歌曲顺序为 4,3,1,2,那么播放列表就会很精彩了，因此不需要删除任何歌曲。

在第三个测试样例中，可以删除歌曲 4,5,6,7。这样，歌曲顺序为 1,2,3 的播放列表就很精彩了。