A graph is said to be a planar graph if it can be drawn on a plane such a way that its edges intersect only at their end points. In other words, it can be drawn in such a way that no edges cross each other.In this problem, you are given a 2-regular connected graph where the n vertices (numbered from 1 to n) are drawn in the perimeter of a circle in clockwise order. Now the graph may or may not be planar. We want to make it planar. We are allowed to move a vertex to any empty place on the perimeter of the circle. When a vertex is moved, its edges will also move with it but remain connected with the vertex.

For example, there is a non-planar graph in the left picture, we made it a planar graph (shown in the right picture) by moving vertex-3 between vertex 1 and 4. There are other solutions, but the best we can do is to move one vertex and make it planar. You have to do the similar task, you are given a graph as described, and your task is to make it planar by moving as few vertices as possible. Assume that the circle is large enough such that you can place any number of vertices between two particular vertices.

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a line containing an integer n (3 ≤ n ≤ 500). Each of the next n lines contains two integers. The i^th line** (1 ≤ i ≤ n)** contains the vertices that have an edge with vertex i. You can assume that the given graph follows the restrictions defined above.

For each case, print the case number first. Then if it's impossible to make it planar, print impossible in the same line. Otherwise, print the minimum possible number of vertices that need to be moved to make the graph planar.

1. A graph is said to be 2-regular if each vertex has exactly two edges.
2. A connected graph is an undirected graph where it's possible to move from any vertex to another using the edges.