Domino

Crazy Cuckoo Charlie is a Computer Science student trying to get his name into the Book of Waterloo Records. Unfortunately, he has no special skills — only a lot of time and a lot of dominoes. He is going to try to break the record for "Waterloo's Longest Domino Chain", which is all about placing as many dominoes end-to-end as possible.

Each domino has two halves, and each half shows a number of dots. To set the record, Charlie must lay all of his dominoes end-to-end in a single line. There is one extra rule: the touching halves of any two neighbouring dominoes must show the same number of dots (as in the picture above).

Charlie wants to use all of his dominoes in the chain. Because of this rule, though, he may not be able to build a chain from the dominoes he owns (for example, with only 1 2 and 4 5 there is no way to connect them). He is willing to buy extra dominoes to complete the chain, and naturally he wants to buy as few as possible so he can save money for more important things like pizza and pop.

Help Charlie find the minimum number of dominoes he must buy so that all of his dominoes can be lined up into a single chain.

The input consists of several test cases, each describing one collection of dominoes. The first line contains an integer $N$, the number of test cases. Each test case begins with a line containing an integer $K$ ($1 < K < 10,000$), the number of dominoes Charlie owns. Each of the next $K$ lines describes one domino in the form A B, where $A$ and $B$ are positive integers giving the number of dots on the two halves ($0 < A < B < 50,000$). Remember that a domino may be flipped around.

For each test case, print on its own line a single integer $X$: the minimum number of dominoes Charlie must buy so that all of his dominoes can be arranged into one chain.

As you learned this week, many problems can be modelled with graphs, and this is one of them.

By the way, an Euler path is a path that traverses every edge of a graph. (This is very different from a Hamiltonian path.) A graph has an Euler path if and only if both of the following hold:

1. The graph is connected (you can get from anywhere to anywhere).
2. The number of vertices with odd degree (the number of edges touching the vertex is odd) is at most two.