POLSKI SPOJ

Dziś są dni otwarte Bajtlandzkiej uczelni. Każdy może zapoznać się z wykładowcami, porozmawiać z nimi na różne tematy i przede wszystkim zmierzyć się z nimi intelektualnie. Profesor Algobit przygotował dla swoich potencjalnych studentów grę domino składającą się z 28 kamieni. Na obydwu końcach każdego klocka znajduje się pewna liczba oczek należąca do zbioru {0, 1, 2, 3, 4, 5, 6} oraz każda kombinacja występuje dokładnie raz. Uczniowie szkół ponadgimnazjalnych chętnie podchodzili do stanowiska profesora będąc przekonani, że za chwilę rozegrają fascynującą grę w domino. Niestety bardzo się mylili. Wykładowca rozdał dwa zestawy po tyle samo kamieni - jeden dla siebie, drugi dla swojego przeciwnika, odkrył wyszystkie kamienie i zadał pytanie: "Jeśli ja zaczynam grę i każdy z nas będzie dokładał kamienie zgodnie z zasadami gry domino w taki sposób, że jeśli po zakończonej grze weźmiemy ze stołu dwa dowolne sąsiadujące ze sobą kamienie, to jeden będzie mój a drugi twój, to ile maksymalnie może znaleźć się kamieni na stole?". Zadanie okazało się twardym orzechem do zgryzienia. Jeśli chcesz podejść do profesora Algobita, to wcześniej napisz program, który rozwiąże tą zagadkę, a wiedz, że wtedy profesor zarekomenduje twoje umiejętności.

Wejś›cie

W pierwszym wierszu liczba n określająca liczbę zestawów danych (n ≤ 103).

Każdy zestaw składa się z jednej liczby n określającej po ile kamieni będzie rozdane dla każdego z przeciwników (n należy do zbioru {1, 2, 3, .., 14}. W następnych dwóch wierszach po dwie porcje po n kamieni domina. Pierwszy zestaw to kamienie prof. Algobita, zaś drugie Twoje.

Każdy kamień jest zapisany w postaci: [liczba oczek]|[liczba oczek] np. 3|0. Liczba oczek to liczba należąca do zbioru {0, 1, 2, 3, 4, 5, 6} oraz kamienie są unikatowe.

Jest tylko kilka przypadków testowych, w których znajduje się maksymalna liczba kamieni.

Wyjś›cie

Dla każdego zestawu jedna liczba określająca maksymalną długość kamieni domina przy optymalnej grze, jeśli wiadomo, że pierszy ruch należy do profesora Algobita.

Przykł‚ad

Wejś›cie:
4
4
1|0 2|1 1|5 2|0 
3|2 3|3 3|0 4|1 
5
6|1 4|6 4|5 6|6 5|3 
4|4 0|1 2|6 0|5 2|4 
3
3|3 0|0 1|2 
4|2 6|1 2|0 
2
3|2 0|6 
2|5 1|6 

Wyjście:
2
4
4
2

Wyjaśnienie dla drugiego zestawu testowego:

Dane kamienie można połączyć w następujący sposób (czerwone kamienie należą do ciebie):
2|6 6|4 4|4 4|5