1554_E. You_129
You are given a tree with n nodes. As a reminder, a tree is a connected undirected graph without cycles.

Let a_1, a_2, …, a_n be a sequence of integers. Perform the following operation exactly n times: 

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



For each integer k from 1 to n, find the number, modulo 998 244 353, of different sequences a_1, a_2, …, a_n that satisfy the following conditions:

  * it is possible to obtain a by performing the aforementioned operations exactly n times in some order. 
  * \operatorname{gcd}(a_1, a_2, …, a_n) = k. Here, \operatorname{gcd} means the greatest common divisor of the elements in a. 

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

The first line of each test case contains a single integer n (2 ≤ n ≤ 10^5).

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

It is guaranteed that the sum of n over all test cases doesn't exceed 3 ⋅ 10^5.

Output

For each test case, print n integers in a single line, where for each k from 1 to n, the k-th integer denotes the answer when \operatorname{gcd} equals to k.

Example

Input


2
3
2 1
1 3
2
1 2


Output


3 1 0
2 0

Note

In the first test case, 

<image>

  * If we delete the nodes in order 1 → 2 → 3 or 1 → 3 → 2, then the obtained sequence will be a = [2, 0, 0] which has \operatorname{gcd} equals to 2. 
  * If we delete the nodes in order 2 → 1 → 3, then the obtained sequence will be a = [1, 1, 0] which has \operatorname{gcd} equals to 1. 
  * If we delete the nodes in order 3 → 1 → 2, then the obtained sequence will be a = [1, 0, 1] which has \operatorname{gcd} equals to 1. 
  * If we delete the nodes in order 2 → 3 → 1 or 3 → 2 → 1, then the obtained sequence will be a = [0, 1, 1] which has \operatorname{gcd} equals to 1. 



Note that here we are counting the number of different sequences, not the number of different orders of deleting nodes.
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
 public class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= 998244353;
    long fac[]= new long[1000001];
    long inv[]=new long[1000001];
    int queue[]=new int[100001];
    boolean visited[]=new boolean[100001];
    int deg[]=new int[100001];
    int a[]=new int[100001];
    public  void solve() throws IOException 
    {

        
         

        int t = readInt();

        for(int f =0;f<t;f++)
        {
             int n = readInt();
             ArrayList<Integer> arr[]=new ArrayList[n+1];
             for(int i=1;i<=n;i++)
                arr[i]= new ArrayList<Integer>();
             for(int i=1;i<=n-1;i++)
             {
                 int u = readInt();
                 int v = readInt();
                 arr[u].add(v);
                 arr[v].add(u);
             }

             ArrayList<Integer> div = new ArrayList<Integer>();

             int root = (int)Math.pow(n-1,0.5);

             if(n-1==1)
             {
                div.add(1);
             }
             else 
             {
                div.add(1);
                div.add(n-1);
                for(int i=2;i<=root;i++)
                {
                     if((n-1)%i==0)
                     {
                        div.add(i);
                        if(i!=((n-1)/i))
                        {
                            div.add((n-1)/i);
                        }
                     }
                }
             }
             Collections.sort(div);

             long dp[]=new long[n+1];


             dp[1]= pow(2,n-1,in);
            // out.println(dp[1]);

             for(int i= div.size()-1;i>=1;i--)
             {
                   int l = div.get(i);
                   if(check(arr,l))
                   {
                     dp[l]=1;
                   }
                   
             }
             for(int i=div.size()-1;i>=0;i--)
             {
                int l = div.get(i);
                for(int j =i+1;j<div.size();j++)
                {
                   int l1= div.get(j);

                   if(l1%l==0)
                   {
                    dp[l]= (dp[l]-dp[l1]+in)%in; 
                   }
                }
             }


             for(int i=1;i<=n;i++)
                out.print(dp[i]+" ");

             out.println();


        }
        



    }
    public boolean check(ArrayList<Integer> arr[], int k )
    {
       int n = arr.length-1;
     //  boolean visited[]=new boolean[n+1];

       for(int i=1;i<=n;i++)
        visited[i]= false;
       int start=0;
       int end=-1;
       for(int i=1;i<=n;i++)
        deg[i]= arr[i].size();
       for(int i=1;i<=n;i++)
        a[i]=0;
       for(int i=1;i<=n;i++)
       {
          if(deg[i]==1)
          {
            end++;
            queue[end]=i;
          }
       }

       while(start<=end)
       {
         int c=queue[start];
         
         visited[c]= true;



         for(int j =0;j<arr[c].size();j++)
         {
            int v = arr[c].get(j);
            if(!visited[v])
            {
                deg[v]--;

                if((a[c]%k)==0)
                {
                    a[v]++;
                }
                else
                {
                    a[c]++;
                }
                if(deg[v]==1)
                {
                    end++;
                    queue[end]=v;
                }
            }

         }

         if((a[c]%k)!=0)
            return false;
         

         start++;
       }

       return true;

    }
    
    public int value (int seg[], int left , int right ,int index, int l, int r)
    {
            
            if(left>right)
            {
              return -100000000;
            }
            if(right<l||left>r)
                return -100000000;
            if(left>=l&&right<=r)
                return seg[index];
            int mid = left+(right-left)/2;
            int val = value(seg,left,mid,2*index+1,l,r);
            int val2 = value(seg,mid+1,right,2*index+2,l,r);
            return Math.max(val,val2);

    }
   
    public int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int u ;
    int v;
    
    edge(int  u, int v)
    {
       this.u=u;
       this.v=v;
    }
    public int compareTo(edge e)
    {
        return this.v-e.v;
    }
}