E

Corrupted Friendship

Many of us know a person named Mr. Haba Kom Khan. He is very corrupted and lazy. He maintains links with a lot of (corrupted) persons. In order to corrupt more lazy persons, he invites his friends in a recursive fashion in a meeting. The idea is:

If X has some cards, he keeps one card and he invites one of his friends Y who has no invitation cards yet and X gives all the remaining cards to Y. Then we say that Y is invited by X. Y then has the responsibility to distribute as many cards as he can, and Y keeps one card and continues the same procedure as X. When Y cannot find any more friends to give the invitation cards, he gives the remaining cards back to X. X then checks for his friends who have no cards yet. If any such friend is found, X continues the same procedure. Otherwise, if X was invited by Z then X gives the remaining cards back to Z. X keeps the cards if there is no such person.

Initially Mr. Haba has N invitations cards, and he starts the invitation process as stated. There are N persons, and they are numbered from 1 to N. Mr. Haba is the person numbered 1. And the strange fact is that, after the invitation process, each person gets exactly 1 card.

Given all the information of persons being invited by others, Mr. Haba wants you to find the total number of invitations that was made. He also asks you to find the number of different pairs of persons who are certainly not friends. Help Mr. Haba Kom Khan to succeed in his corrupted life!

Input

The first line of input will contain T (≤ 30) denoting the number of cases.

Each case starts with an integer N (1 ≤ N ≤ 105). Each of the next N-1 lines will contain two integers, X and Y (1 ≤ X, Y ≤ N, X ≠ Y) denoting that person Y received his invitation card from person X. Input is huge. So, faster I/O methods (e.g. scanf, printf, BufferedReader, BufferedWriter) are recommended.

Output

For each case, print the case number, total number of invitations made, and the number of different pairs of persons who are surely not friends. See samples for detailed formatting.

Sample Input

Output for Sample Input

 
2
2
1 2
3
1 2
1 3
 
Case 1: 1 0
Case 2: 2 1
 

Problem Setter: Shahriar Rouf Nafi, Special Thanks: Jane Alam Jan