Apollo isn't well prepared on geometry problems, but he heard that this year there will be a lot of geometry problems on the ICPC. Scared, Apollo locked himself in the basement and started thinking of new problems of this kind. One of them is the following.

Given n segments (numbered from 1 to n) in the two dimensional space. The i-th segment connects the points and . Apollo wants to select n points from the given n segments. The i-th point should lie in the i-th segment. That is say, the i-th points should meet and .
The Euclidean distance between the two points with numbers i and j is said to be: . We say that the length of the path formed by the n points is value .

Apollo gives you the starting and ending points of n segments. You have to find n points for him, to minumize the length of the path formed by the n points.

The first line is an integer  (), which is the number of test cases.
Each test case begins with a line containing a positive integer n () showing the number of segments. The following n lines contain the descriptions of the n segments. Each line contains two integers  and  () --- the coordinates of the two endpoints for one of the i-th segment are  and .

For each test case, output one line containing "Case #x:", where x is the test case number, and next n lines print the n points that you selected. The i-th line is " ", denotes the coordinate of the i-th point.
It may have multiple solutions, you can output any of them. Let the length of your answer be a, and the length of jury's answer be b. Your answer is considered correct, if .

2
4
1 3
0 2
2 3
1 4
5
1 2
1 3
2 3
3 4
2 4

Case #1:
1 2
2 2
3 2
4 2
Case #2:
1 2.000000
2 2.333333
3 2.666667
4 3.000000
5 3.000000