#include <bits/stdc++.h>
using namespace std;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template <typename A, typename B>
ostream& operator<<(ostream& cout, pair<A, B> const& p) {
  return cout << "(" << p.first << ", " << p.second << ")";
}
template <typename A>
ostream& operator<<(ostream& cout, vector<A> const& v) {
  cout << "[";
  for (int i = 0; i < (int)v.size(); i++) {
    if (i) cout << ", ";
    cout << v[i];
  }
  return cout << "]";
}
template <typename T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
typedef std::decay<decltype(998244353)>::type mod_t;
struct mi {
  mod_t val;
  explicit operator mod_t() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-998244353 <= v && v < 998244353) ? v : v % 998244353;
    if (val < 0) val += 998244353;
  }
  friend std::istream& operator>>(std::istream& in, mi& a) {
    long long x;
    std::cin >> x;
    a = mi(x);
    return in;
  }
  friend std::ostream& operator<<(std::ostream& os, const mi& a) {
    return os << a.val;
  }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  friend bool operator>(const mi& a, const mi& b) { return a.val > b.val; }
  friend bool operator<=(const mi& a, const mi& b) { return a.val <= b.val; }
  friend bool operator>=(const mi& a, const mi& b) { return a.val >= b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= 998244353) val -= 998244353;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += 998244353;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % 998244353;
    return *this;
  }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a != 0);
    return pow(a, 998244353 - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  for (int ti = 0; ti < (t); ti++) {
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (int i = 0; i < (n - 1); i++) {
      int x, y;
      cin >> x >> y;
      x--;
      y--;
      adj[x].push_back(y);
      adj[y].push_back(x);
    }
    vector<mi> v(n);
    bool good;
    function<bool(int, int, int)> check = [&](int u, int par, int k) {
      int x = 0;
      for (int oth : adj[u])
        if (oth != par) x += check(oth, u, k);
      if (x % k == 0) {
        return true;
      }
      if ((x + 1) % k == 0) {
        return false;
      }
      good = false;
      return false;
    };
    for (int k = 2; k <= n; k++) {
      if ((n - 1) % k) continue;
      good = true;
      if (!check(0, -1, k)) good = false;
      if (good) {
        v[k - 1] = true;
      }
    }
    for (int k = n; k >= 2; k--) {
      for (int z = k + k; z <= n; z += k) {
        if (v[z - 1] > 0) v[k - 1] = 0;
      }
    }
    v[0] = pow((mi)2, n - 1);
    for (int i = 1; i < n; i++) {
      v[0] -= v[i];
    }
    for (int i = 0; i < (n); i++) cout << v[i] << " ";
    cout << "\n";
  }
}

### Prompt

Create a solution in CPP for 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;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template <typename A, typename B>
ostream& operator<<(ostream& cout, pair<A, B> const& p) {
  return cout << "(" << p.first << ", " << p.second << ")";
}
template <typename A>
ostream& operator<<(ostream& cout, vector<A> const& v) {
  cout << "[";
  for (int i = 0; i < (int)v.size(); i++) {
    if (i) cout << ", ";
    cout << v[i];
  }
  return cout << "]";
}
template <typename T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
typedef std::decay<decltype(998244353)>::type mod_t;
struct mi {
  mod_t val;
  explicit operator mod_t() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-998244353 <= v && v < 998244353) ? v : v % 998244353;
    if (val < 0) val += 998244353;
  }
  friend std::istream& operator>>(std::istream& in, mi& a) {
    long long x;
    std::cin >> x;
    a = mi(x);
    return in;
  }
  friend std::ostream& operator<<(std::ostream& os, const mi& a) {
    return os << a.val;
  }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  friend bool operator>(const mi& a, const mi& b) { return a.val > b.val; }
  friend bool operator<=(const mi& a, const mi& b) { return a.val <= b.val; }
  friend bool operator>=(const mi& a, const mi& b) { return a.val >= b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= 998244353) val -= 998244353;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += 998244353;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % 998244353;
    return *this;
  }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a != 0);
    return pow(a, 998244353 - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  for (int ti = 0; ti < (t); ti++) {
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (int i = 0; i < (n - 1); i++) {
      int x, y;
      cin >> x >> y;
      x--;
      y--;
      adj[x].push_back(y);
      adj[y].push_back(x);
    }
    vector<mi> v(n);
    bool good;
    function<bool(int, int, int)> check = [&](int u, int par, int k) {
      int x = 0;
      for (int oth : adj[u])
        if (oth != par) x += check(oth, u, k);
      if (x % k == 0) {
        return true;
      }
      if ((x + 1) % k == 0) {
        return false;
      }
      good = false;
      return false;
    };
    for (int k = 2; k <= n; k++) {
      if ((n - 1) % k) continue;
      good = true;
      if (!check(0, -1, k)) good = false;
      if (good) {
        v[k - 1] = true;
      }
    }
    for (int k = n; k >= 2; k--) {
      for (int z = k + k; z <= n; z += k) {
        if (v[z - 1] > 0) v[k - 1] = 0;
      }
    }
    v[0] = pow((mi)2, n - 1);
    for (int i = 1; i < n; i++) {
      v[0] -= v[i];
    }
    for (int i = 0; i < (n); i++) cout << v[i] << " ";
    cout << "\n";
  }
}

```