SP211 PRIMIT - Primitivus recurencis

**A genetic code** of the abstract primitivus (_Primitivus recurencis_) is a series of natural numbers _K=_(_a\_1,...,a\_n_). **A feature** of primitivus we call each ordered pair of numbers (_l_,_r_), which appears successively in the genetic code, i.e. there exists such _i_ that _l=a\_i, r=a\_i+1_. There are no (_p_,_p_) features in a primitivus' genetic code. ### Task Write a program which: - reads the list of the features from the standard input, - computes the length of the shortest genetic code having given features, - writes the results to the standard output.

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case one positive integer number _n_ is written. It is the number of different features of the primitivus. In each of the following _n_ lines there is a pair of natural numbers _l_ and _r_ separated by a single space, _1

Your program should write for each test case exactly one integer number equal to the length of the shortest genetic code of the primitivus, comprising the features from the input.