#1054 Our Summer Is Not Over Yet.

Statement

Statement language

Ako	Testing, testing. Can you hear me? Field operatives on standby, please respond.
Iori	This is Codename S. I have arrived on site.
Chinatsu	This is Codename H. I have arrived as well.
Ako	Yes, communications are clear. Everyone is accounted for. Now, I will go over the outline of this operation once more.
Ako	The Prefect Team’s summer training camp ends today at 4 p.m., when we are scheduled to return.
Ako	The only item on today’s schedule that we told the Head Prefect about was the group shooting practice this afternoon.
Ako	However, before that practice, she wished to take some time to practice swimming at the beach.
Ako	Which means... this is proof that she, too, has begun to think of this time as a vacation!
Ako	Then our mission is simple. We must support her vacation with everything we have, right to the end!
Ako	Specifically, we will eliminate any potential dangers on the beach and secure the area, setting the stage for her to enjoy her vacation!
Iori	No matter how I look at it, isn’t this an abuse of power...?
Chinatsu	At least there are no visitors after the previous commotion...
Ako	Enough back talk! Please! There must be absolutely no mistakes!

Hello. I am Ako, senior administrator of Gehenna Academy’s Prefect Team. Until 4 p.m. today, we will have complete control of the beach so that the Head Prefect can practice swimming safely. To that end, I will now prepare the deployment schedule for our operatives.

$\rule{30em}{0.3pt}$

The operation is divided into $N$ deployment slots, numbered $1$ through $N$ . Exactly $1$ field operative is assigned to each slot. There are also $N$ operatives, numbered $1$ through , and each operative will be deployed exactly once today.

Input

The first line contains the number of test cases $T$ . $(1 \le T \le 100\,000)$

For each test case, the first line contains $N$ . The next $N - 1$ lines describe the allowed deployment intervals. The -th of these lines contains , , separated by a space. ;

Output

For each test case, print the following three integers in order, separated by spaces on one line.

The number of pairs $(A_N, B_N)$ for which no valid schedule exists.
The number of pairs $(A_N, B_N)$ for which exactly one valid schedule exists.

Samples

Sample 1

Input

Output

3 3
3 6
1 0

Sample 2

Input

Output

0 0 55