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; 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 starts with an integer T (≤ 30), denoting the number of test cases.

Each case starts with an integer N (1 ≤ N ≤ 10⁵). 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.

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.

Dataset is huge, use faster I/O methods.