description: 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.
solution: #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;
  }
  