#include <bits/stdc++.h>
using namespace std;
template <typename T>
void rd(T& x) {
  int f = 0, c;
  while (!isdigit(c = getchar())) f ^= !(c ^ 45);
  x = (c & 15);
  while (isdigit(c = getchar())) x = x * 10 + (c & 15);
  if (f) x = -x;
}
template <typename T>
void pt(T x, int c = -1) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) pt(x / 10);
  putchar(x % 10 + 48);
  if (c != -1) putchar(c);
}
const int P = 998244353;
int ad(int k1, int k2) { return k1 += k2 - P, k1 += k1 >> 31 & P; }
int su(int k1, int k2) { return k1 -= k2, k1 += k1 >> 31 & P; }
int mu(int k1, int k2) { return 1LL * k1 * k2 % P; }
void uad(int& k1, int k2) { k1 += k2 - P, k1 += k1 >> 31 & P; }
void usu(int& k1, int k2) { k1 -= k2, k1 += k1 >> 31 & P; }
template <typename... T>
int ad(int k1, T... k2) {
  return ad(k1, ad(k2...));
}
template <typename... T>
void uad(int& k1, T... k2) {
  return uad(k1, ad(k2...));
}
template <typename... T>
void usu(int& k1, T... k2) {
  return usu(k1, ad(k2...));
}
template <typename... T>
int mu(int k1, T... k2) {
  return mu(k1, mu(k2...));
}
int po(int k1, int k2) {
  int k3 = 1;
  for (; k2; k2 >>= 1, k1 = mu(k1, k1))
    if (k2 & 1) k3 = mu(k3, k1);
  return k3;
}
namespace ntt {
int base = 1, root = -1, maxbase = -1;
std::vector<int> roots = {0, 1}, rev = {0, 1};
void init() {
  int tmp = P - 1;
  maxbase = 0;
  while (!(tmp & 1)) tmp >>= 1, maxbase++;
  root = 2;
  while (1) {
    if (po(root, 1 << maxbase) == 1 && po(root, 1 << (maxbase - 1)) != 1) break;
    root++;
  }
}
void ensure_base(int nbase) {
  if (maxbase == -1) init();
  if (nbase <= base) return;
  rev.resize(1 << nbase);
  for (int i = 1; i < (1 << nbase); ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (nbase - 1));
  roots.resize(1 << nbase);
  while (base < nbase) {
    int z = po(root, 1 << (maxbase - base - 1));
    for (int i = (1 << (base - 1)); i < (1 << base); ++i)
      roots[i << 1] = roots[i], roots[i << 1 | 1] = mu(roots[i], z);
    base++;
  }
}
void dft(std::vector<int>& a) {
  int n = a.size(), zeros = __builtin_ctz(n);
  ensure_base(zeros);
  int shift = base - zeros;
  for (int i = 0; i < n; ++i)
    if (i < (rev[i] >> shift)) std::swap(a[i], a[rev[i] >> shift]);
  for (int mid = 1; mid < n; mid <<= 1)
    for (int i = 0; i < n; i += (mid << 1))
      for (int j = 0; j < mid; ++j) {
        int x = a[i + j], y = mu(a[i + j + mid], roots[mid + j]);
        a[i + j] = ad(x, y);
        a[i + j + mid] = su(x, y);
      }
}
std::vector<int> operator*(std::vector<int> a, std::vector<int> b) {
  if (((int)(a).size()) <= 50 && ((int)(b).size()) <= 50) {
    vector<int> c(((int)(a).size()) + ((int)(b).size()) - 1);
    for (int i = (0); i <= (((int)(a).size()) - 1); ++i)
      for (int j = (0); j <= (((int)(b).size()) - 1); ++j)
        uad(c[i + j], mu(a[i], b[j]));
    return c;
  }
  int need = a.size() + b.size() - 1, nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  int size = 1 << nbase;
  a.resize(size);
  b.resize(size);
  dft(a);
  dft(b);
  int inv = po(size, P - 2);
  for (int i = 0; i < size; ++i) a[i] = mu(a[i], mu(b[i], inv));
  std::reverse(a.begin() + 1, a.end());
  dft(a);
  a.resize(need);
  return a;
}
}  // namespace ntt
using ntt::operator*;
const int N = 100005;
int T, n, K, deg[N], f[N], dp[N][2];
int pp, lnk[N], nxt[N * 2], to[N * 2];
vector<int> e;
void ae(int k1, int k2) { to[++pp] = k2, nxt[pp] = lnk[k1], lnk[k1] = pp; }
vector<int> prod(int l, int r) {
  if (l == r) {
    if (K == 1) return {ad(dp[e[l]][1], dp[e[l]][0])};
    return {dp[e[l]][1], dp[e[l]][0]};
  }
  int mid = (l + r) >> 1;
  auto res = prod(l, mid) * prod(mid + 1, r);
  while (((int)(res).size()) > K) {
    uad(res[((int)(res).size()) - 1 - K], res.back());
    res.pop_back();
  }
  return res;
}
void dfs(int k1, int k2) {
  for (int i = lnk[k1]; i; i = nxt[i])
    if (to[i] != k2) {
      dfs(to[i], k1);
    }
  dp[k1][0] = dp[k1][1] = 0;
  if (deg[k1] >= K) {
    e.clear();
    int pos = 0, val = 1;
    for (int i = lnk[k1]; i; i = nxt[i])
      if (to[i] != k2) {
        if (dp[to[i]][1] == 0) {
          if (++pos == K) pos = 0;
          val = mu(val, dp[to[i]][0]);
        } else
          e.push_back(to[i]);
      }
    if (e.empty()) {
      dp[k1][0] = pos == 0 ? val : 0, dp[k1][1] = pos == K - 1 ? val : 0;
    } else {
      auto v = prod(0, ((int)(e).size()) - 1);
      auto get = [&](int x) { return x < ((int)(v).size()) ? v[x] : 0; };
      dp[k1][0] = mu(val, get((K - pos) % K)),
      dp[k1][1] = mu(val, get((K - 1 - pos) % K));
    }
  } else {
    dp[k1][0] = 1;
    for (int i = lnk[k1]; i; i = nxt[i])
      if (to[i] != k2) {
        dp[k1][0] = mu(dp[k1][0], dp[to[i]][1]);
      }
  }
}
int main() {
  rd(T);
  while (T--) {
    rd(n);
    for (int i = (1); i <= (n); ++i) lnk[i] = 0, deg[i] = 0, f[i] = 0;
    pp = 0;
    for (int i = (2); i <= (n); ++i) {
      int k1, k2;
      rd(k1), rd(k2);
      ae(k1, k2), ae(k2, k1);
      ++deg[k1], ++deg[k2];
    }
    int lim = n;
    for (int k1 = (1); k1 <= (n); ++k1)
      for (int i = lnk[k1]; i; i = nxt[i]) {
        lim = min(lim, max(deg[k1], deg[to[i]]));
      }
    for (K = 1; K <= lim; ++K)
      if ((n - 1) * 2 % K == 0) {
        dfs(1, 0);
        f[K] = dp[1][0];
      }
    for (int i = (lim); i >= (1); --i) {
      for (int j = i + i; j <= lim; j += i) {
        usu(f[i], f[j]);
      }
    }
    for (int i = (1); i <= (n); ++i) pt(f[i], i == n ? '\n' : ' ');
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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;
template <typename T>
void rd(T& x) {
  int f = 0, c;
  while (!isdigit(c = getchar())) f ^= !(c ^ 45);
  x = (c & 15);
  while (isdigit(c = getchar())) x = x * 10 + (c & 15);
  if (f) x = -x;
}
template <typename T>
void pt(T x, int c = -1) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) pt(x / 10);
  putchar(x % 10 + 48);
  if (c != -1) putchar(c);
}
const int P = 998244353;
int ad(int k1, int k2) { return k1 += k2 - P, k1 += k1 >> 31 & P; }
int su(int k1, int k2) { return k1 -= k2, k1 += k1 >> 31 & P; }
int mu(int k1, int k2) { return 1LL * k1 * k2 % P; }
void uad(int& k1, int k2) { k1 += k2 - P, k1 += k1 >> 31 & P; }
void usu(int& k1, int k2) { k1 -= k2, k1 += k1 >> 31 & P; }
template <typename... T>
int ad(int k1, T... k2) {
  return ad(k1, ad(k2...));
}
template <typename... T>
void uad(int& k1, T... k2) {
  return uad(k1, ad(k2...));
}
template <typename... T>
void usu(int& k1, T... k2) {
  return usu(k1, ad(k2...));
}
template <typename... T>
int mu(int k1, T... k2) {
  return mu(k1, mu(k2...));
}
int po(int k1, int k2) {
  int k3 = 1;
  for (; k2; k2 >>= 1, k1 = mu(k1, k1))
    if (k2 & 1) k3 = mu(k3, k1);
  return k3;
}
namespace ntt {
int base = 1, root = -1, maxbase = -1;
std::vector<int> roots = {0, 1}, rev = {0, 1};
void init() {
  int tmp = P - 1;
  maxbase = 0;
  while (!(tmp & 1)) tmp >>= 1, maxbase++;
  root = 2;
  while (1) {
    if (po(root, 1 << maxbase) == 1 && po(root, 1 << (maxbase - 1)) != 1) break;
    root++;
  }
}
void ensure_base(int nbase) {
  if (maxbase == -1) init();
  if (nbase <= base) return;
  rev.resize(1 << nbase);
  for (int i = 1; i < (1 << nbase); ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (nbase - 1));
  roots.resize(1 << nbase);
  while (base < nbase) {
    int z = po(root, 1 << (maxbase - base - 1));
    for (int i = (1 << (base - 1)); i < (1 << base); ++i)
      roots[i << 1] = roots[i], roots[i << 1 | 1] = mu(roots[i], z);
    base++;
  }
}
void dft(std::vector<int>& a) {
  int n = a.size(), zeros = __builtin_ctz(n);
  ensure_base(zeros);
  int shift = base - zeros;
  for (int i = 0; i < n; ++i)
    if (i < (rev[i] >> shift)) std::swap(a[i], a[rev[i] >> shift]);
  for (int mid = 1; mid < n; mid <<= 1)
    for (int i = 0; i < n; i += (mid << 1))
      for (int j = 0; j < mid; ++j) {
        int x = a[i + j], y = mu(a[i + j + mid], roots[mid + j]);
        a[i + j] = ad(x, y);
        a[i + j + mid] = su(x, y);
      }
}
std::vector<int> operator*(std::vector<int> a, std::vector<int> b) {
  if (((int)(a).size()) <= 50 && ((int)(b).size()) <= 50) {
    vector<int> c(((int)(a).size()) + ((int)(b).size()) - 1);
    for (int i = (0); i <= (((int)(a).size()) - 1); ++i)
      for (int j = (0); j <= (((int)(b).size()) - 1); ++j)
        uad(c[i + j], mu(a[i], b[j]));
    return c;
  }
  int need = a.size() + b.size() - 1, nbase = 0;
  while ((1 << nbase) < need) nbase++;
  ensure_base(nbase);
  int size = 1 << nbase;
  a.resize(size);
  b.resize(size);
  dft(a);
  dft(b);
  int inv = po(size, P - 2);
  for (int i = 0; i < size; ++i) a[i] = mu(a[i], mu(b[i], inv));
  std::reverse(a.begin() + 1, a.end());
  dft(a);
  a.resize(need);
  return a;
}
}  // namespace ntt
using ntt::operator*;
const int N = 100005;
int T, n, K, deg[N], f[N], dp[N][2];
int pp, lnk[N], nxt[N * 2], to[N * 2];
vector<int> e;
void ae(int k1, int k2) { to[++pp] = k2, nxt[pp] = lnk[k1], lnk[k1] = pp; }
vector<int> prod(int l, int r) {
  if (l == r) {
    if (K == 1) return {ad(dp[e[l]][1], dp[e[l]][0])};
    return {dp[e[l]][1], dp[e[l]][0]};
  }
  int mid = (l + r) >> 1;
  auto res = prod(l, mid) * prod(mid + 1, r);
  while (((int)(res).size()) > K) {
    uad(res[((int)(res).size()) - 1 - K], res.back());
    res.pop_back();
  }
  return res;
}
void dfs(int k1, int k2) {
  for (int i = lnk[k1]; i; i = nxt[i])
    if (to[i] != k2) {
      dfs(to[i], k1);
    }
  dp[k1][0] = dp[k1][1] = 0;
  if (deg[k1] >= K) {
    e.clear();
    int pos = 0, val = 1;
    for (int i = lnk[k1]; i; i = nxt[i])
      if (to[i] != k2) {
        if (dp[to[i]][1] == 0) {
          if (++pos == K) pos = 0;
          val = mu(val, dp[to[i]][0]);
        } else
          e.push_back(to[i]);
      }
    if (e.empty()) {
      dp[k1][0] = pos == 0 ? val : 0, dp[k1][1] = pos == K - 1 ? val : 0;
    } else {
      auto v = prod(0, ((int)(e).size()) - 1);
      auto get = [&](int x) { return x < ((int)(v).size()) ? v[x] : 0; };
      dp[k1][0] = mu(val, get((K - pos) % K)),
      dp[k1][1] = mu(val, get((K - 1 - pos) % K));
    }
  } else {
    dp[k1][0] = 1;
    for (int i = lnk[k1]; i; i = nxt[i])
      if (to[i] != k2) {
        dp[k1][0] = mu(dp[k1][0], dp[to[i]][1]);
      }
  }
}
int main() {
  rd(T);
  while (T--) {
    rd(n);
    for (int i = (1); i <= (n); ++i) lnk[i] = 0, deg[i] = 0, f[i] = 0;
    pp = 0;
    for (int i = (2); i <= (n); ++i) {
      int k1, k2;
      rd(k1), rd(k2);
      ae(k1, k2), ae(k2, k1);
      ++deg[k1], ++deg[k2];
    }
    int lim = n;
    for (int k1 = (1); k1 <= (n); ++k1)
      for (int i = lnk[k1]; i; i = nxt[i]) {
        lim = min(lim, max(deg[k1], deg[to[i]]));
      }
    for (K = 1; K <= lim; ++K)
      if ((n - 1) * 2 % K == 0) {
        dfs(1, 0);
        f[K] = dp[1][0];
      }
    for (int i = (lim); i >= (1); --i) {
      for (int j = i + i; j <= lim; j += i) {
        usu(f[i], f[j]);
      }
    }
    for (int i = (1); i <= (n); ++i) pt(f[i], i == n ? '\n' : ' ');
  }
  return 0;
}

```