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). 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 contain