After having been wandering around Madrid for several hours, you finally reach the NH Zurbano hotel where all competitors will be located for the SWERC weekend. Each team received an ID number when it registered for SWERC. At your arrival, the receptionist at NH Zurbano asks you for that ID number and assigns you a room according to your team’s registration ID and the one of the delegations that arrived prior to you.

The hotel is as long and as high that it would be possible to accommodate all delegations either on the same floor or on different floors each. The elevator is at the reception side (left) and rooms are located at the first floor and above, on the right-hand side to the elevator. Now the receptionist’s room assignment strategy is the following:

The receptionist takes you with the elevator to the first floor. Then you walk along the corridor until you arrive at a room that currently hosts a delegation with larger ID than yours. If no such team is on that floor, you get the first empty room you come across. In the opposite case, the team that currently occupies the room has to free it for you! Then the receptionist takes this team to the second floor and uses the same method to find a new room for this team. If the receptionist brings a team to a floor on which currently no other team is hosted, it is assigned the first room at that floor.

Although this placement strategy seems quite unorthodox, some members of the EPFL delegation got used to interlaced travel and rest, especially at airports and railway stations. Instead of being shocked by the fact of having to potentially change the room as further delegations arrive, your coach is even more impressed by that placement strategy and challenges you with the following question:

Given the current assignment of the rooms, can you list all possible orders of arrival of the teams?

Input

The first line contains the number of test cases C (C≤25). Each test case starts with the number of occupied floors F. The following F lines contain information about floors F, …, 1, starting from the top. First on each of these lines is an integer N, the number of teams at that floor. Following that, there are N integers on the line: the ID of the teams on that floor, starting from the elevator side (left). All IDs satisfy (1≤ID≤60). There are never more than T (T≤15) teams in the hotel at the moment your coach challenges you. A blank line precedes each test case.

Output

For each test case, output first the number of the test case, then the number P of possible arrival orders. See the sample output for the exact format.

On the following min(10, P) lines, print the lexicographically smallest possible arrival orders.

Example

Input:
2

3
1 3
2 2 9
3 1 4 5

2
1 3
2 1 2

Output:
Case 1 : 16
3 2 1 4 9 5
3 2 1 9 4 5
3 2 4 1 9 5
3 2 4 9 1 5
3 2 4 9 5 1
3 2 9 1 4 5
3 2 9 4 1 5
3 2 9 4 5 1
3 4 2 1 9 5
3 4 2 9 1 5

Case 2 : 2
1 3 2
3 1 2