Sea Voyage

Manao has won several boat ride tickets.
Each ticket lists two cities. A ticket can be used exactly once, but Manao can choose the direction in which to travel between the two cities.

Manao loves ships and the sea, and he wants to use all of the tickets he has won. However, in some cases, he might need to buy additional tickets to make this possible. Manao lives in BATUMI, and his entire journey must start and end there.

You may assume that it is always possible to buy a ticket between any pair of cities, including between BATUMI and any other city.

You are given a description of the tickets Manao already has. Determine:

The minimum number of additional tickets Manao needs to buy in order to use all of his tickets in a single journey starting and ending in BATUMI.
The list of the additional tickets he should buy.
If there are multiple valid solutions, output any one of them.

Constraints

The number of tickets Manao already has, denoted $M$ , satisfies $1 \leq M \leq 100$ .
Each city name consists of a single word of uppercase Latin letters with length at most $20$ .
Each ticket is represented by two distinct city names.

Input Format

The first line contains an integer $T$ — the number of test cases.

Each test case has the following format:

The first line contains an integer $M$ — the number of tickets Manao already has.
The next $M$ lines each contain two city names, representing one ticket.

Output Format

For each test case $i$ ( $1 \leq i \leq T$ ):

On the first line, output Case #i: K, where $K$ is the minimum number of additional tickets Manao needs to buy.
Then output $K$ lines, each containing two city names, representing the additional tickets to be purchased.

If there are multiple valid solutions, output any one of them.

Example

Input:

2
4
BATUMI TRABZON
ODESSA CONSTANTA
ODESSA TRABZON
ODESSA ISTANBUL
2
SAMSUN TRABZON
BURGAS VARNA

Output:

Case #1: 2
BATUMI ODESSA
CONSTANTA ISTANBUL
Case #2: 3
BURGAS SAMSUN
TRABZON BATUMI
BATUMI VARNA

Explanation:

For test case 1, take a look at the map below. The routes for tickets Manao already owns are colored red,
whereas the routes for suggested ticket purchases are colored green. With these 2 new tickets,
Manao can embark on the following voyage:
BATUMI -> ODESSA -> CONSTANTA -> ISTANBUL -> ODESSA -> TRABZON -> BATUMI.

black sea map

For test case 2, Manao needs 3 additional tickets.

The first ticket connects BATUMI to one of the cities from the existing tickets.
The second ticket links the two separate routes formed by the existing tickets.
The third ticket brings Manao back from the other route to BATUMI.