You solution codeforces

You solution codeforces


You are given a tree with nn nodes. As a reminder, a tree is a connected undirected graph without cycles.

Let a1,a2,,ana1,a2,…,an be a sequence of integers. Perform the following operation exactly nn times:

  • Select an unerased node uu. Assign au:=au:= number of unerased nodes adjacent to uu. Then, erase the node uu along with all edges that have it as an endpoint.

For each integer kk from 11 to nn, find the number, modulo 998244353998244353, of different sequences a1,a2,,ana1,a2,…,an that satisfy the following conditions:

  • it is possible to obtain aa by performing the aforementioned operations exactly nn times in some order.
  • gcd(a1,a2,,an)=kgcd⁡(a1,a2,…,an)=k. Here, gcdgcd means the greatest common divisor of the elements in aa.
Input

The first line contains a single integer tt (1t100001≤t≤10000)  — the number of test cases.

The first line of each test case contains a single integer nn (2n1052≤n≤105).

Each of the next n1n−1 lines contains two integers uu and vv (1u,vn1≤u,v≤n) indicating there is an edge between vertices uu and vv. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of nn over all test cases doesn’t exceed 31053⋅105.

Output

For each test case, print nn integers in a single line, where for each kk from 11 to nn, the kk-th integer denotes the answer when gcdgcd equals to kk.

Example

input

Copy
2
3
2 1
1 3
2
1 2

output

Copy
3 1 0
2 0
Note

In the first test case,

You solution codeforces

  • If we delete the nodes in order 1231→2→3 or 1321→3→2, then the obtained sequence will be a=[2,0,0]a=[2,0,0] which has gcdgcd equals to 22.
  • If we delete the nodes in order 2132→1→3, then the obtained sequence will be a=[1,1,0]a=[1,1,0] which has gcdgcd equals to 11.
  • If we delete the nodes in order 3123→1→2, then the obtained sequence will be a=[1,0,1]a=[1,0,1] which has gcdgcd equals to 11.
  • If we delete the nodes in order 2312→3→1 or 3213→2→1, then the obtained sequence will be a=[0,1,1]a=[0,1,1] which has gcdgcd equals to 11.

Note that here we are counting the number of different sequences, not the number of different orders of deleting nodes.


Leave a Comment