311214: CF1950G. Shuffling Songs

G. Shuffling Songstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Vladislav has a playlist consisting of $n$ songs, numbered from $1$ to $n$. Song $i$ has genre $g_i$ and writer $w_i$. He wants to make a playlist in such a way that every pair of adjacent songs either have the same writer or are from the same genre (or both). He calls such a playlist exciting. Both $g_i$ and $w_i$ are strings of length no more than $10^4$.

It might not always be possible to make an exciting playlist using all the songs, so the shuffling process occurs in two steps. First, some amount (possibly zero) of the songs are removed, and then the remaining songs in the playlist are rearranged to make it exciting.

Since Vladislav doesn't like when songs get removed from his playlist, he wants the making playlist to perform as few removals as possible. Help him find the minimum number of removals that need to be performed in order to be able to rearrange the rest of the songs to make the playlist exciting.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 16$) — the number of songs in the original playlist.

Then $n$ lines follow, the $i$-th of which contains two strings of lowercase letters $g_i$ and $w_i$ ($1 \leq |g_i|, |w_i| \leq 10^4$) — the genre and the writer of the $i$-th song. Where $|g_i|$ and $|w_i|$ are lengths of the strings.

The sum of $2^n$ over all test cases does not exceed $2^{16}$.

The sum of $|g_i| + |w_i|$ over all test cases does not exceed $4 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum number of removals necessary so that the resulting playlist can be made exciting.

ExampleInput

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

Output

0
0
4
3

Note

In the first test case, the playlist is already exciting.

In the second test case, if you have the songs in the order $4, 3, 1, 2$, it is exciting, so you don't need to remove any songs.

In the third test case, you can remove songs $4, 5, 6, 7$. Then the playlist with songs in the order $1, 2, 3$ is exciting.

题目大意：
Vladislav有一个播放列表，包含n首歌曲，编号从1到n。每首歌i有一个流派g_i和一个作者w_i。他想以这样的方式制作播放列表：每对相邻的歌曲要么有相同的作者，要么属于同一流派（或者两者都有）。他把这样的播放列表称为"exciting"。g_i和w_i都是长度不超过10^4的字符串。

可能无法总是使用所有歌曲制作一个exciting播放列表，因此洗牌过程分为两步。首先，删除一些歌曲（可能为零首），然后重新排列播放列表中剩余的歌曲以使其变得exciting。

由于Vladislav不喜欢他的播放列表中的歌曲被删除，他希望制作播放列表时执行的删除操作尽可能少。帮助他找到需要执行的最少删除次数，以便能够重新排列其余的歌曲以制作一个exciting播放列表。

输入数据格式：
输入的第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数n（1≤n≤16）——原始播放列表中的歌曲数量。

然后是n行，每行包含两个由小写字母组成的字符串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。

输出数据格式：
对于每个测试用例，输出一个整数——为了使结果播放列表变得exciting，需要执行的最少删除次数。题目大意： Vladislav有一个播放列表，包含n首歌曲，编号从1到n。每首歌i有一个流派g_i和一个作者w_i。他想以这样的方式制作播放列表：每对相邻的歌曲要么有相同的作者，要么属于同一流派（或者两者都有）。他把这样的播放列表称为"exciting"。g_i和w_i都是长度不超过10^4的字符串。 可能无法总是使用所有歌曲制作一个exciting播放列表，因此洗牌过程分为两步。首先，删除一些歌曲（可能为零首），然后重新排列播放列表中剩余的歌曲以使其变得exciting。 由于Vladislav不喜欢他的播放列表中的歌曲被删除，他希望制作播放列表时执行的删除操作尽可能少。帮助他找到需要执行的最少删除次数，以便能够重新排列其余的歌曲以制作一个exciting播放列表。 输入数据格式： 输入的第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤16）——原始播放列表中的歌曲数量。 然后是n行，每行包含两个由小写字母组成的字符串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。 输出数据格式： 对于每个测试用例，输出一个整数——为了使结果播放列表变得exciting，需要执行的最少删除次数。