Drawing Simple Polygon

1 seconds
64 MB
Hard
LOJ-1285 Udebug Debug
English

Given set of points in the plane, your task is to draw a polygon using the points. You have to use all the points. To be more specific, each point of the set has to be a vertex of the polygon, and the polygon must not have any other vertices. No two line segments of the polygon may have any point in common, except for the middle vertex of two consecutive line segments. For example, given the points on the left-hand side, a valid polygon is shown on the right-hand side:

Given Points Valid Solution

You can assume that, no two points will share the same location.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.Each case starts with a line containing an integer n (3 ≤ n ≤ 2000), denoting the number of points. The next line contains the co-ordinates of the points. Each point is specified by two integer x y in the range [-104, 104].

Output

For each case, print the case number in a single line first. In the next line print Impossible if no solution can be found. Otherwise print a permutation of the numbers 0 to n-1. Each of these numbers represents the index of a point, in the same order as given in the input. When drawing line segments between consecutive points in the order given by this permutation, the result must be a valid polygon. Insert a single space between two integers.

Sample

Sample Input Sample Output

2 4 0 0 2 0 0 1 1 0 5 0 0 10 0 10 5 5 -1 0 5

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

Notes

This is a special judge problem; wrong output format may cause wrong answer.