Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has a tree with n vertices, the length of each edge is exactly 1. For any none empty subset S of the vertices, value(S) is equal to max(dis(u,v))(u,v \in S) which dis(u,v) is equal to the distance between u and v on the tree.

It is easy to find that value(S) satisfy 0<=value(S)<n. Now For each K in [0,n), Yuta wants to know the number of the subset S which satisfy value(S)=K.

It is too difficult for Rikka. Can you help her?

Input

The first line contains a number t(1<=t<=100), the number of the testcases. And there are no more than 5 testcases with n>100.

For each testcase, the first line contains a number n(1<=n<=3000). Then n-1 lines follow, each line contains two numbers u and v, which means there is an edge between u and v.

Output

For each testcase, print a line contains exactly n numbers, the ith number is the number of none empty subsets S which satisfy value(S)=i-1. The answer may be very large, so you only need to print the answer module 998244353.

2
2
1 2
4
1 3
2 4
4 1

2 1
4 3 4 4

Author

学军中学