题目描述

Vladislav 有一个包含 $n$ 首歌的歌单，歌曲编号 $1$ 到 $n$。第 $i$ 首歌的流派是 $g_i$，作者是 $w_i$。他希望整理出一个歌单，使得任意相邻两首歌要么作者相同、要么流派相同（或者两者都相同）。这样的歌单他称之为带感的（exciting）。$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$。

输出格式

对每组数据，输出一个整数，表示最少需要删掉的歌曲数。

说明

第一组数据中，歌单本身已经是带感的。

第二组数据中，按 $4, 3, 1, 2$ 的顺序排列是带感的，所以不需要删歌。

第三组数据中，删掉第 $4, 5, 6, 7$ 首歌后，按 $1, 2, 3$ 的顺序排列是带感的。

样例

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

来源

Codeforces Round 937 (Div. 4) G 题