Description

Xiao Y recently acquired a random number generator. She wants to use this generator to create trees with $n$ nodes. A tree is an undirected connected graph with no cycles.

Through her research, she discovered 4 methods for generating random trees:

• Method 1: First, generate a random permutation $p_1, p_2, \dots, p_n$ of $1$ to $n$. Then, for all nodes $i$ ($2 \le i \le n$), add an edge between $p_i$ and $p_j$, where $j$ is a random integer from $1$ to $i-1$.
• Method 2: First, generate a random permutation $p_1, p_2, \dots, p_n$ of $1$ to $n$. Then, for all nodes $i$ ($2 \le i \le n$), add an edge between $p_i$ and $p_j$, where $j$ is a random integer from $\lfloor i/2 \rfloor$ to $i-1$.
• Method 3: Start with a graph of $n$ nodes and no edges. Then, randomly select a pair of nodes $(u, v)$ with equal probability. If $u$ and $v$ are not currently connected in the graph, add the edge $(u, v)$ to the graph. Repeat this process until the graph is connected.
• Method 4: Uniformly select a tree at random from all possible labeled trees with $n$ nodes. Two trees are different if and only if there exists an edge $(u, v)$ that appears in one tree but not the other. For example, $\{(1,2), (1,3)\}$ and $\{(1,2), (2,3)\}$ are two different trees.

Xiao Y used these four methods to generate many trees with $n$ nodes, but she forgot which method generated which tree. Can you help her identify the generation method for each tree?

In this problem, $n = 1000$, meaning all trees generated by Xiao Y have 1000 nodes.

Input

The first line contains a single positive integer $T$, representing the number of test cases.

Next, a positive integer $m$ is given, representing the number of trees.

For each tree, there are $n-1$ lines. Each line contains two positive integers $u, v$, representing an edge between node $u$ and node $v$ in the tree.

Output

Output $m$ lines, each containing a single integer between 1 and 4, representing the method used to generate that tree.

Constraints

For all test data, it is guaranteed that the input trees are generated by the four methods described above.

The test cases satisfy the following conditions:

For each test case, it is guaranteed that each possible generation method appears exactly 1000 times.

Subtasks

For each test case, there are 10 scoring parameters $a_{10}, a_9, a_8, \dots, a_1$.

If the number of incorrect answers in your output is $x$, you will receive a score of $2s$, where $s$ is the largest integer such that $x \le a_s$. If $x > a_1$, you will receive 0 points.

If the output format is incorrect, you will also receive 0 points. Please ensure your output contains exactly $m$ lines, each containing an integer between 1 and 4.

The specific scoring parameters for each test case can be found in the file rng/scores in the contestant's directory.

Examples

Input 1

(See rng/rng.in in the contestant's directory)

Output 1

(See rng/rng.ans in the contestant's directory)