#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const long long mod = 998244353;
inline long long gcd(long long a, long long b) {
  return !b ? a : gcd(b, a % b);
}
inline long long q_pow(long long a, long long x) {
  long long ans = 1, tmp = a;
  while (x) {
    if (x & 1) (ans *= tmp) %= mod;
    (tmp *= tmp) %= mod;
    x >>= 1;
  }
  return ans;
}
template <typename T>
inline void re(T &N) {
  int f = 1;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') f = -1;
  N = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') N = N * 10 + c - '0';
  N *= f;
}
template <class T, class... T_>
inline void re(T &x, T_ &...y) {
  re(x), re(y...);
}
int m, n, t = 1, st, en;
struct edge {
  int to, nxt;
} e[N << 1];
int head[N];
inline void add(int x, int y) {
  e[++t] = {y, head[x]};
  head[x] = t;
  e[++t] = {x, head[y]};
  head[y] = t;
}
int a[N], ok = 1;
void dfs(int x, int p, int k) {
  a[x] = 0;
  for (int i = head[x]; i; i = e[i].nxt) {
    int to = e[i].to;
    if (to == p) continue;
    dfs(to, x, k);
    if (a[to] % k)
      a[to]++;
    else
      a[x]++;
    if (a[to] % k) ok = 0;
  }
}
int check(int k) {
  ok = 1;
  dfs(1, 0, k);
  if (a[1] % k) ok = 0;
  return ok;
}
int p[N], v[N], ma_p[N], mi_p[N];
int phi[N], miu[N];
void get_prime() {
  phi[1] = miu[1] = 1;
  ma_p[1] = mi_p[1] = 1;
  for (int i = 2; i <= N - 1; i++) {
    if (!v[i])
      v[i] = i, p[++p[0]] = i, mi_p[i] = ma_p[i] = i, phi[i] = i - 1,
      miu[i] = -1;
    for (int j = 1; j <= p[0]; j++) {
      if (p[j] > v[i] || p[j] > (N - 1) / i) break;
      int nxt = i * p[j];
      v[nxt] = p[j];
      ma_p[nxt] = ma_p[i];
      mi_p[nxt] = p[j];
      phi[nxt] = phi[i] * (i % p[j] ? p[j] - 1 : p[j]);
      miu[nxt] = miu[i] * (i % p[j] ? -1 : 0);
    }
  }
}
long long f[N], g[N];
int main() {
  get_prime();
  int T;
  re(T);
  while (T--) {
    re(n);
    t = 1;
    for (int i = 1; i <= n; i++) head[i] = f[i] = g[i] = 0;
    for (int i = 1; i < n; i++) {
      int x, y;
      re(x, y);
      add(x, y);
    }
    if (n == 2) {
      puts("2 0");
      continue;
    }
    f[1] = q_pow(2, n - 1);
    f[n - 1] = check(n - 1);
    for (int i = 2; i * i <= n - 1; i++)
      if (!((n - 1) % i)) {
        f[i] = check(i);
        f[(n - 1) / i] = check((n - 1) / i);
      }
    for (int i = 1; i <= n; i++)
      for (int j = i; j <= n; j += i) g[i] += miu[j / i] * f[j];
    for (int i = 1; i <= n; i++) printf("%lld ", (g[i] % mod + mod) % mod);
    puts("");
  }
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const long long mod = 998244353;
inline long long gcd(long long a, long long b) {
  return !b ? a : gcd(b, a % b);
}
inline long long q_pow(long long a, long long x) {
  long long ans = 1, tmp = a;
  while (x) {
    if (x & 1) (ans *= tmp) %= mod;
    (tmp *= tmp) %= mod;
    x >>= 1;
  }
  return ans;
}
template <typename T>
inline void re(T &N) {
  int f = 1;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') f = -1;
  N = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') N = N * 10 + c - '0';
  N *= f;
}
template <class T, class... T_>
inline void re(T &x, T_ &...y) {
  re(x), re(y...);
}
int m, n, t = 1, st, en;
struct edge {
  int to, nxt;
} e[N << 1];
int head[N];
inline void add(int x, int y) {
  e[++t] = {y, head[x]};
  head[x] = t;
  e[++t] = {x, head[y]};
  head[y] = t;
}
int a[N], ok = 1;
void dfs(int x, int p, int k) {
  a[x] = 0;
  for (int i = head[x]; i; i = e[i].nxt) {
    int to = e[i].to;
    if (to == p) continue;
    dfs(to, x, k);
    if (a[to] % k)
      a[to]++;
    else
      a[x]++;
    if (a[to] % k) ok = 0;
  }
}
int check(int k) {
  ok = 1;
  dfs(1, 0, k);
  if (a[1] % k) ok = 0;
  return ok;
}
int p[N], v[N], ma_p[N], mi_p[N];
int phi[N], miu[N];
void get_prime() {
  phi[1] = miu[1] = 1;
  ma_p[1] = mi_p[1] = 1;
  for (int i = 2; i <= N - 1; i++) {
    if (!v[i])
      v[i] = i, p[++p[0]] = i, mi_p[i] = ma_p[i] = i, phi[i] = i - 1,
      miu[i] = -1;
    for (int j = 1; j <= p[0]; j++) {
      if (p[j] > v[i] || p[j] > (N - 1) / i) break;
      int nxt = i * p[j];
      v[nxt] = p[j];
      ma_p[nxt] = ma_p[i];
      mi_p[nxt] = p[j];
      phi[nxt] = phi[i] * (i % p[j] ? p[j] - 1 : p[j]);
      miu[nxt] = miu[i] * (i % p[j] ? -1 : 0);
    }
  }
}
long long f[N], g[N];
int main() {
  get_prime();
  int T;
  re(T);
  while (T--) {
    re(n);
    t = 1;
    for (int i = 1; i <= n; i++) head[i] = f[i] = g[i] = 0;
    for (int i = 1; i < n; i++) {
      int x, y;
      re(x, y);
      add(x, y);
    }
    if (n == 2) {
      puts("2 0");
      continue;
    }
    f[1] = q_pow(2, n - 1);
    f[n - 1] = check(n - 1);
    for (int i = 2; i * i <= n - 1; i++)
      if (!((n - 1) % i)) {
        f[i] = check(i);
        f[(n - 1) / i] = check((n - 1) / i);
      }
    for (int i = 1; i <= n; i++)
      for (int j = i; j <= n; j += i) g[i] += miu[j / i] * f[j];
    for (int i = 1; i <= n; i++) printf("%lld ", (g[i] % mod + mod) % mod);
    puts("");
  }
}

```