G. Перемешивание песен
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Владислава есть плейлист, состоящий из $$$n$$$ песен, пронумерованных от $$$1$$$ до $$$n$$$. Песня $$$i$$$ имеет жанр $$$g_i$$$ и автора $$$w_i$$$. Он хочет составить плейлист таким образом, чтобы каждая пара соседних песен либо имела одного и того же автора, либо была из того же жанра (или и то, и другое). Он называет такой плейлист захватывающим. И $$$g_i$$$, и $$$w_i$$$ являются строками, длины не более $$$10^4$$$.

Не всегда возможно составить захватывающий плейлист, используя все песни, поэтому процесс перемешивания происходит в два этапа. Сначала удаляются некоторое количество (возможно, нулевое) песен, а затем оставшиеся песни в плейлисте переставляются, чтобы сделать его захватывающим.

Поскольку Владислав не любит, когда песни удаляются из его плейлиста, он хочет, чтобы составление плейлиста выполнялось с минимальным количеством удалений. Помогите ему найти минимальное количество удалений, которые необходимо выполнить, чтобы можно было переставить оставшиеся песни, чтобы сделать плейлист захватывающим.

Входные данные

Первая строка ввода содержит одно целое число $$$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
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
Примечание

В первом тесте плейлист уже захватывающий.

Во втором тесте, если у вас есть песни в порядке $$$4, 3, 1, 2$$$, это захватывающий плейлист, поэтому вам не нужно удалять никакие песни.

В третьем тесте вы можете удалить песни $$$4, 5, 6, 7$$$. Тогда плейлист с песнями в порядке $$$1, 2, 3$$$ будет захватывающим.