题目描述

弗拉迪斯拉夫有一个播放列表，其中包含 $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 的播放列表就很令人兴奋了。