Despite what the problem name suggests, we hope that this problem is not NP-hard.

This is an interactive problem.

Given a rooted tree$$$^{\text{∗}}$$$ $$$T$$$ of size $$$m$$$, where each node $$$i$$$ has an associated value $$$a_i$$$, define a vertical path as a sequence of nodes $$$[s_1,s_2,\ldots,s_p]$$$ such that $$$s_{i+1}$$$ is a child of $$$s_i$$$ for all $$$1 \leq i \lt p$$$. A vertical path is good if $$$\operatorname{gcd}(a_{s_1},a_{s_2},\ldots,a_{s_p}) \neq 1$$$$$$^{\text{†}}$$$. Define $$$f(T)$$$ as the minimum number of good vertical paths such that every node is in exactly one good path.

There is a strange rooted tree of $$$n$$$ nodes, where node $$$1$$$ is the root. The tree satisfies the property that each node only has children with labels greater than itself. Denote $$$S(u)$$$ as the subtree of node $$$u$$$. That is, $$$S(u)$$$ contains all nodes $$$v$$$ such that the shortest path from node $$$1$$$ to node $$$v$$$ contains node $$$u$$$, and all edges where both endpoints are between two such nodes.

You are interested in finding $$$f(S(n)), f(S(n-1)), \ldots, f(S(1))$$$. However, there is a magical oracle that is hiding information about the tree from you! Specifically, the oracle only tells you information about vertex $$$x$$$ after reading your result of $$$f(S(x+1))$$$. In other words, you must solve this problem online, starting from node $$$n$$$ and ending at node $$$1$$$.

$$$^{\text{∗}}$$$A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root. The parent of vertex $$$v$$$ is the first vertex on the simple path from $$$v$$$ to the root. The root has no parent. A child of vertex $$$v$$$ is any vertex $$$u$$$ for which $$$v$$$ is the parent.

$$$^{\text{†}}$$$Here, $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) – denoting the number of nodes in the tree.

Then $$$n$$$ lines follow. The $$$i$$$-th line of them will contain information about node $$$j=n-i+1$$$, in the following format.

$$$a_j \; k \; c_1 \; c_2 \; \ldots \; c_k$$$: Node $$$j=n-i+1$$$ has an associated value $$$a_j$$$ and $$$k$$$ children with node labels $$$c_1,c_2,\ldots,c_k$$$.

For each node $$$j$$$, it is guaranteed that $$$2 \le a_j \le 10^{18}$$$ and $$$j+1 \le c_i \le n$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$.

It is guaranteed that the sum of $$$k$$$ over all nodes in one test case is exactly $$$n-1$$$, and the edges form a valid rooted tree.

Output

For each test case, you must output $$$n$$$ lines, where the $$$i$$$-th line of them contains the value of $$$f(S(n-i+1))$$$.

Do note that this problem is technically interactive. Specifically, the interactor will give you the next piece of information only after reading your line of output.

After printing each line, you must output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

$$$^{\text{∗}}$$$To flush, use:

fflush(stdout) or cout.flush() in C++;
sys.stdout.flush() in Python;
see the documentation for other languages.

Note

In the first test case, since all values of $$$a_i$$$ are coprime, it is impossible to cover more than one node with each path. Therefore, the value of $$$f(S(1))$$$ is $$$5$$$.

In the second test case, we can verify that $$$f(S(1))=4$$$ with the following $$$4$$$ vertical paths:

$$$[1,2]$$$. The GCD of this vertical path is $$$\operatorname{gcd}(2,4)=2$$$.
$$$[3]$$$. The GCD of this vertical path is $$$\operatorname{gcd}(6)=6$$$.
$$$[4]$$$. The GCD of this vertical path is $$$\operatorname{gcd}(8)=8$$$.
$$$[5]$$$. The GCD of this vertical path is $$$\operatorname{gcd}(10)=10$$$.

Since no vertical path has a GCD of $$$1$$$, this solution is valid. Additionally, we can show that it is impossible to cover all nodes with fewer than $$$4$$$ vertical paths.

Minimum Path Cover

Examples