PEG Judge - CCC04 Stage 2

2004 Canadian Computing Competition, Stage 2

Day 1, Problem 2: Hockey Scores

Hugh Hockey is a very big hockey fan. Every Saturday night he sits and watches all the hockey games, never wanting to miss a moment. Every Canadian loves hockey.

Not this Saturday night though. Hugh Hockey has a date, so he trained his three year-old brother Billy to record the scores for him. He sits Billy in front of his TV, teaches him how to change the channels, and tells him to write down the hockey scores.

Hugh returns home, after his date, to a surprise: he discovers that even though Billy wrote down the scores, Billy didn't write down the names of the teams. He also discovered that Billy not only wrote down the final scores, but also the scores of games in progress. To make matters worse, Billy didn't follow any specific order when writing down the score of a game; A score of two-to-one could have been written down as 2 - 1 or 1 - 2. There's no guarantee that Billy wrote down every score, some could be missed.

Help Hugh figure out, from Billy's list, the minimum number of hockey games that occured, so Hugh knows, sadly, how much hockey he's missed.

Input

Input consists of a series of test cases. The first line consists of an integer n, the number of test cases.

For each test case, the first line consists of the integer s, (1 ≤ s ≤ 1000), the number of hockey scores recorded by Billy. The next s lines each contain a hockey score in the form x - y, where x and y are non-negative integers.

Output

For each test case, output on a single line the integer m, the minimum number of games that must have occured such that each score Billy recorded occurs in a game sometime during the night. The next m lines give a possible scenario for the hockey games, such that each score Billy recorded is used at least once (and scores that Billy did not record do not appear).

If there is more than one possible scenario for the hockey scores, any one will do.