SP5014 CRAZYR - Crazy Receptionist

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?

The first line contains the number of test cases C (C

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.