SP34009 CTTC - Counting Child

Little boy Arik is playing with tree. He is counting the number of children of each node. For this, he starts with root node 1. And traverse the full tree in DFS (Depth First Search) style. For simplicity, see the following figure. For Tree - 1, his traversing sequence is 1 2 2 3 3 1. He starts with root node 1. Then he starts visiting first child 2, then finishes his traversing at 2. Then he starts visiting second child 3, then finishes his traversing at 3. And then finally finishes his traversing at 1. For Tree - 2, his traversing sequence is 1 2 4 4 2 3 5 5 6 6 3 1.

Input starts with an integer t (1

For each case print the case number in the first line. Following n lines print each node from 1 to n and number of child of the node. Print a blank line after each test cases. See the sample I/O section for more details about output format.