// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 1e3 + 14, B = 60;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll x, y;
        cin >> x >> y;
        if (y > x) {
            cout << "-1\n";
            continue;
        }
        bool seen = false;
        for (int i = B - 1; i >= 0; --i) {
            if ((x >> i & 1) > (y >> i & 1))
                seen = true;
            if (seen && (x >> i & 1) == 0) {
                x ^= (1ll << i + 1);
                x |= (1ll << i + 1) - 1;
                break;
            }
        }
        if (popcount((unsigned long long) x) == 1)
            cout << (1ll << popcount((unsigned long long) x)) - (y == 0) << '\n';
        else
            cout << (1ll << popcount((unsigned long long) x)) - (y != 0) << '\n';
    }
}

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 1e6 + 1, MAX_P = MAX_N * 2;
int mark[MAX_N], mat[MAX_N][2], is_prime[MAX_P], par[MAX_N];
vector<int> g[MAX_N], cer_prefix[MAX_N], cer_suffix[MAX_N];

bool dfs(int v) {
    if (mark[v])
        return 0;
    mark[v] = 1;
    for (auto u : g[v])
        if (mat[u][1] == -1 || dfs(mat[u][1]))
            return mat[v][0] = u, mat[u][1] = v, 1;
    return 0;
}

int maximum_matching(int l, int n) {
    fill(mat[l], mat[n + 1], -1);
    bool br = 0;
    int ans = 0;
    while (br ^= 1) {
        fill(mark + l, mark + n + 1, false);
        for (int i = l; i <= n; i++)
            if (mat[i][0] == -1 && dfs(i))
                ans++, br = 0;
    }
    return ans;
}

void print(int n) {
    if (n == 0)
        return;
    if (n == 1) {
        cout << "1 ";
        return;
    }
    if (par[n] == -1) {
        for (int i = n; i >= 1; i--) {
            if (i % 2 == 1) {
                for (int j = i + 1; j <= n; j += 2)
                    if (is_prime[i + j])
                        g[i].push_back(j);
            }
            else
                for (int j = i + 1; j <= n; j += 2)
                    if (is_prime[i + j])
                        g[j].push_back(i);
            if (i % 2 != n % 2 && maximum_matching(i, n) == (n - i) / 2 + 1) {
                for (int j = i; j <= n; ++j) {
                    if (j % 2) {
                        cer_prefix[n].push_back(j);
                        cer_suffix[n].push_back(mat[j][0]);
                    }
                    g[j].clear();
                }
                ranges::reverse(cer_suffix[n]);
                par[n] = i - 1;
                break;
            }
        }
    }
    for (auto x : cer_prefix[n])
        cout << x << ' ';
    print(par[n]);
    for (auto x : cer_suffix[n])
        cout << x << ' ';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fill_n(is_prime, MAX_P, true);
    for (int p = 2; p * p < MAX_P; ++p)
        for (int i = p * p; i < MAX_P; i += p)
            is_prime[i] = false;
    fill_n(par, MAX_N, -1);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        print(n);
        cout << '\n';
    }
}

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;

struct ModInt {
    int x;

    bool operator==(const ModInt& rhs) const {
        return x == rhs.x;
    }

    bool operator!=(const ModInt& rhs) const {
        return !(rhs == *this);
    }

    ModInt(ll x = 0) : x(((x % MOD) + MOD) % MOD) {
    }

    friend ModInt operator+(const ModInt& l, const ModInt& r) {
        return l.x + r.x;
    }

    ModInt& operator+=(const ModInt& o) {
        return *this = *this + o;
    }

    friend ModInt operator-(const ModInt& l, const ModInt& r) {
        return l.x - r.x;
    }

    ModInt operator-() const {
        return -x;
    }

    ModInt& operator-=(const ModInt& o) {
        return *this = *this - o;
    }

    friend ModInt operator*(const ModInt& l, const ModInt& r) {
        return (ll)l.x * r.x;
    }

    ModInt& operator*=(const ModInt& o) {
        return *this = *this * o;
    }

    ModInt pow(ll b) const {
        ModInt ans = 1;
        ModInt a = *this;
        for (; b; b >>= 1, a = a * a)
            if (b & 1)
                ans *= a;
        return ans;
    }

    ModInt rev() const {
        return pow(MOD - 2);
    }

    friend ModInt operator/(const ModInt& l, const ModInt& r) {
        return l * r.rev();
    }

    ModInt& operator/=(const ModInt& o) {
        return *this = *this / o;
    }

    friend ostream& operator<<(ostream& os, const ModInt& anInt) {
        os << anInt.x;
        return os;
    }
};


const int MAX_N = 2e2 + 14, D = 10;
int n, k;
ModInt cache[2][D][D][D][D][2 * D], zero, one = 1;
ModInt dp(int n, int last, int max_streak, int streak_l, int streak_r);

ModInt& dp(int n, int last, int l, int r, int max_streak, int streak) {
    if (last < 0 || last >= D)
        return zero;
    if (n == 1)
        return streak == 0 && l <= last && last <= r ? one : zero;
    return cache[n & 1][last][l][r][max_streak][streak + D];
}

ModInt dp(int n, int last, int l, int r, int max_streak, int streak_l, int streak_r) {
    ModInt ans = 0;
    for (int s = streak_l; s <= streak_r; ++s)
        ans += dp(n, last, l, r, max_streak, s);
    return ans;
}

ModInt dp(int n, int last, int l, int r, int max_streak) {
    return dp(n, last, l, r, max_streak, -max_streak, max_streak) - (max_streak
                                                                         ? dp(n, last, l, r, max_streak - 1,
                                                                              -max_streak + 1, max_streak - 1)
                                                                         : 0);
}

ModInt dp_pure(int n, int last, int l, int r, int max_streak) {
    assert(l <= r);
    if (l == r)
        return dp(n, last, l, r, max_streak);
    return dp(n, last, l, r, max_streak) - dp(n, last, l + 1, r, max_streak) - dp(n, last, l, r - 1, max_streak) + dp(
        n, last, l + 1, r - 1, max_streak);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 2; i <= n; ++i) {
        fill(cache[i & 1][0][0][0][0], cache[(i & 1) + 1][0][0][0][0], ModInt());
        for (int l = 0; l < D; ++l)
            for (int r = 0; r < D; ++r)
                for (int last = i == n ? 0 : l; last <= (i == n ? D - 1 : r); ++last)
                    for (int max_streak = 0; max_streak < D; ++max_streak)
                        for (int streak = -max_streak; streak <= max_streak; ++streak) {
                            ModInt& ans = dp(i, last, l, r, max_streak, streak);
                            if (streak > 1)
                                ans = dp(i - 1, last - 1, l, r, max_streak, streak - 1);
                            else if (streak < -1)
                                ans = dp(i - 1, last + 1, l, r, max_streak, streak + 1);
                            else if (streak == 0)
                                ans = dp(i - 1, last, l, r, max_streak, -max_streak, max_streak);
                            else if (streak == 1)
                                ans = dp(i - 1, last - 1, l, r, max_streak, -max_streak, 0);
                            else if (streak == -1)
                                ans = dp(i - 1, last + 1, l, r, max_streak, 0, max_streak);
                        }
    }

    ModInt ans;
    for (int i = 0; i < D; ++i) {
        for (int row_streak = -D + 1; row_streak < D; ++row_streak)
            for (int col_streak = -D + 1; col_streak < D; ++col_streak)
                if ((row_streak + 1) * (col_streak + 1) <= k)
                    for (int l = 0; l < D; ++l)
                        for (int r = l; r < D; ++r) {
                            int cl = max(0, i - l), cr = min(D - 1, D - 1 + i - r);
                            ans += dp_pure(n, i, l, r, row_streak) * dp(n, i, cl, cr, col_streak);
                        }
    }
    cout << ans << '\n';
}

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14;

int ask(int i, int j, int k) {
    cout << "? " << i + 1 << ' ' << j + 1 << ' ' << k + 1 << endl;
    int x;
    cin >> x;
    return x;
}

int main() {
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        int a[4];
        a[0] = ask(1, 2, 3);
        a[1] = ask(0, 2, 3);
        a[2] = ask(0, 1, 3);
        a[3] = ask(0, 1, 2);
        int p[n];
        for (int i = 0; i < 4; ++i)
            p[i] = accumulate(a, a + 4, 0) / 3 - a[i];
        for (int i = 4; i < n; ++i)
            p[i] = ask(0, 1, i) - p[0] - p[1];
        cout << "! ";
        for (int i = 0; i < n; ++i)
            cout << p[i] << " ";
        cout << endl;
    }
}

t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    s = input()
    ans = s[0]
    sum = 0
    for i in range(1, n):
        if s[i] == ans[-1] or (i + 1 < n and s[i] == s[i + 1]):
            sum += ans[-1] == s[i]
            ans += s[i]
    print(sum)

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        int mn = *min_element(a, a + n);
        cout << mn * (ll) n + n - count(a, a + n, mn) << endl;
    }
}

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;

struct ModInt {
    int x;

    bool operator==(const ModInt& rhs) const {
        return x == rhs.x;
    }

    bool operator!=(const ModInt& rhs) const {
        return !(rhs == *this);
    }

    ModInt(ll x = 0) : x(((x % MOD) + MOD) % MOD) {
    }

    friend ModInt operator+(const ModInt& l, const ModInt& r) {
        return l.x + r.x;
    }

    ModInt& operator+=(const ModInt& o) {
        return *this = *this + o;
    }

    friend ModInt operator-(const ModInt& l, const ModInt& r) {
        return l.x - r.x;
    }

    ModInt operator-() const {
        return -x;
    }

    ModInt& operator-=(const ModInt& o) {
        return *this = *this - o;
    }

    friend ModInt operator*(const ModInt& l, const ModInt& r) {
        return (ll)l.x * r.x;
    }

    ModInt& operator*=(const ModInt& o) {
        return *this = *this * o;
    }

    ModInt pow(ll b) const {
        ModInt ans = 1;
        ModInt a = *this;
        for (; b; b >>= 1, a = a * a)
            if (b & 1)
                ans *= a;
        return ans;
    }

    ModInt rev() const {
        return pow(MOD - 2);
    }

    friend ModInt operator/(const ModInt& l, const ModInt& r) {
        return l * r.rev();
    }

    ModInt& operator/=(const ModInt& o) {
        return *this = *this / o;
    }

    friend ostream& operator<<(ostream& os, const ModInt& anInt) {
        os << anInt.x;
        return os;
    }
};


const int MAX_N = 1e6 + 1;

int phi[MAX_N];

ModInt factor[MAX_N], ans[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 1; i < MAX_N; i++) {
        phi[i] += i;
        for (int j = i * 2; j < MAX_N; j += i)
            phi[j] -= phi[i];
    }

    fill_n(factor, MAX_N, 1);
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;
        factor[a] *= (ModInt(a) / phi[a] + 1);
    }

    ModInt total;

    for (int i = MAX_N - 1; i >= 1; i--) {
        ans[i] = 1;
        for (int j = i; j < MAX_N; j += i)
            ans[i] *= factor[j];
        for (int j = i * 2; j < MAX_N; j += i)
            ans[i] -= ans[j];
        ans[i] -= 1;
        total += ans[i] / i;
    }
    cout << total << '\n';
}

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int B = 20, MAX_N = 1 << B;

const int MOD = 1e9 + 7;

struct ModInt {
    int x;

    bool operator==(const ModInt& rhs) const {
        return x == rhs.x;
    }

    bool operator!=(const ModInt& rhs) const {
        return !(rhs == *this);
    }

    ModInt(ll x = 0) : x(((x % MOD) + MOD) % MOD) {
    }

    explicit operator int() const {
        return x;
    }

    friend ModInt operator+(const ModInt& l, const ModInt& r) {
        return l.x + r.x;
    }

    ModInt& operator+=(const ModInt& o) {
        return *this = *this + o;
    }

    friend ModInt operator-(const ModInt& l, const ModInt& r) {
        return l.x - r.x;
    }

    ModInt operator-() const {
        return -x;
    }

    ModInt& operator-=(const ModInt& o) {
        return *this = *this - o;
    }

    friend ModInt operator*(const ModInt& l, const ModInt& r) {
        return (ll)l.x * r.x;
    }

    ModInt& operator*=(const ModInt& o) {
        return *this = *this * o;
    }

    ModInt pow(ll b) const {
        ModInt ans = 1;
        ModInt a = *this;
        for (; b; b >>= 1, a = a * a)
            if (b & 1)
                ans *= a;
        return ans;
    }

    ModInt rev() const {
        return pow(MOD - 2);
    }

    friend ModInt operator/(const ModInt& l, const ModInt& r) {
        return l * r.rev();
    }

    ModInt& operator/=(const ModInt& o) {
        return *this = *this / o;
    }

    friend ostream& operator<<(ostream& os, const ModInt& anInt) {
        os << anInt.x;
        return os;
    }
};

ModInt fac[MAX_N] = {1}, rfac[MAX_N] = {1};

ModInt c(int n, int r) {
    return n < r || r < 0 ? 0 : fac[n] * rfac[r] * rfac[n - r];
}

void prep() {
    for (int i = 1; i < MAX_N; ++i)
        fac[i] = fac[i - 1] * i;
    rfac[MAX_N - 1] = fac[MAX_N - 1].rev();
    for (int i = MAX_N - 2; i >= 0; --i)
        rfac[i] = (i + 1) * rfac[i + 1];
}


ModInt cnt[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    prep();
    int n, k;
    cin >> n >> k;
    while (n--) {
        int a;
        cin >> a;
        cnt[a] += 1;
    }
    for (int i = 0; i < B; ++i)
        for (int mask = 0; mask < MAX_N; ++mask)
            if (mask >> i & 1)
                cnt[mask] += cnt[mask ^ (1 << i)];
    for (auto& dp : cnt)
        dp = c((int) dp, k);
    for (int i = 0; i < B; ++i)
        for (int mask = 0; mask < MAX_N; ++mask)
            if (mask >> i & 1)
                cnt[mask] -= cnt[mask ^ (1 << i)];
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << cnt[x] << '\n';
    }
}

B = 30
MOD = 10 ** 9 + 7


def count(n, b):
    return n // (2 ** (b + 1)) * 2 ** b + max(0, n % (2 ** (b + 1)) - 2 ** b)


t = int(input())
while t > 0:
    t -= 1
    c, n = map(int, input().split())
    if c == 1:
        a = [i for i in range(n)]
        for i in range(2, n - 1, 4):
            a[i], a[i + 1] = a[i + 1], a[i]
        if n % 4 == 3:
            a = [a[-2]] + a[:-2] + [a[-1]]
        print(*a)
    else:
        ans = 0
        for b in range(B):
            ones = count(n, b)
            zeros = n - ones
            cur_ans = (ones // 2) * (ones // 2 + 1)
            if ones % 2 == 1:
                cur_ans += ones // 2 + 1
            cur_ans += (ones + 1) // 2 * zeros
            ans += cur_ans * 2 ** b
        print(ans % MOD)

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


const int B = 30;
const int MOD = 1e9 + 7;

long long count(long long n, int b) {
    long long cycle = 1LL << (b + 1);
    long long full = n / cycle;
    long long res = full * (1LL << b);
    long long rem = n % cycle;
    long long add = max(0LL, rem - (1LL << b));
    return res + add;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int c;
        long long n;
        cin >> c >> n;
        if (c == 1) {
            int m = static_cast<int>(n);
            vector<int> a(m);
            for (int i = 0; i < m; ++i) {
                a[i] = i;
            }
            for (int i = 2; i < m - 1; i += 4) {
                swap(a[i], a[i + 1]);
            }
            if (m % 4 == 3) {
                vector<int> new_a;
                new_a.push_back(a[m - 2]);
                for (int i = 0; i < m - 2; ++i) {
                    new_a.push_back(a[i]);
                }
                new_a.push_back(a[m - 1]);
                a = new_a;
            }
            for (size_t i = 0; i < a.size(); ++i) {
                if (i != 0) {
                    cout << ' ';
                }
                cout << a[i];
            }
            cout << endl;
        } else {
            long long ans = 0;
            for (int b = 0; b < B; ++b) {
                long long ones = count(n, b);
                long long zeros = n - ones;
                long long half = ones / 2;
                long long cur_ans = half * (half + 1) % MOD;
                if (ones % 2 == 1) {
                    cur_ans += half + 1;
                }
                cur_ans += ((ones + 1) / 2) * zeros % MOD;
                ans = (ans + cur_ans * (1LL << b)) % MOD;
            }
            ans %= MOD;
            cout << ans << endl;
        }
    }
}

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n], prefix_gcd[n + 1] = {};
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            prefix_gcd[i + 1] = gcd(prefix_gcd[i], a[i]);
        }
        int suffix_gcd = 0, ans = 1;
        for (int i = n - 1; i >= 0; --i) {
            ans = max(ans, gcd(prefix_gcd[i], suffix_gcd));
            suffix_gcd = gcd(suffix_gcd, a[i]);
        }
        cout << ans << '\n';
    }
}

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14;

vector<int> g[MAX_N];
map<int, ll> cache[MAX_N];

ll solve(int v, int k) {
    if (cache[v].count(k))
        return cache[v][k];
    ll& ans = cache[v][k];
    ans = (v + 1) ^ k;
    vector<array<ll, 2>> child;
    for (auto u : g[v])
        if (k % g[v].size())
            child.push_back({solve(u, k / g[v].size()), solve(u, k / g[v].size() + 1)});
        else
            ans += solve(u, k / g[v].size());
    if (g[v].empty() || k % g[v].size() == 0)
        return ans;
    sort(child.begin(), child.end(), [](array<ll, 2> a, array<ll, 2> b) {
        return a[1] - a[0] > b[1] - b[0];
    });
    for (int i = 0; i < child.size(); ++i)
        ans += child[i][i < k % child.size()];
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        for (int i = 1; i < n; ++i) {
            int p;
            cin >> p;
            --p;
            g[p].push_back(i);
        }
        cout << solve(0, k) << '\n';
        fill(g, g + n, vector<int>());
        fill(cache, cache + n, map<int, ll>());
    }
}

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14, LG = 17;

int n, a[MAX_N], st[MAX_N], ft[MAX_N], sp[LG][MAX_N];
vector<int> g[MAX_N], appear[MAX_N];

void dfs(int v = 0, int p = -1) {
    static int time = 0;
    sp[0][time] = a[v];
    appear[a[v]].push_back(time);
    st[v] = time++;
    for (int u : g[v])
        if (u != p)
            dfs(u, v);
    ft[v] = time;
}

int count(int x, int l, int r) {
    return ranges::lower_bound(appear[x], r) - ranges::lower_bound(appear[x], l);
}

int get(int l, int r, int c1, int c2) {
    return get<1>(max(tuple{count(c1, l, r), c1}, tuple{count(c2, l, r), c2}));
}

int king(int l, int r) {
    int ans = 0;
    int p = l;
    for (int i = 0; i < LG; ++i)
        if (r - p >> i & 1) {
            ans = get(l, r, ans, sp[i][p]);
            p += 1 << i;
        }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v;
        --u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dfs();
    for (int k = 1; k < LG; ++k)
        for (int i = 0; i + (1 << k) <= n; ++i)
            sp[k][i] = get(i, i + (1 << k), sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        int sz = st[v] - st[u] + ft[u] - ft[v];
        if (!(st[u] <= st[v] && ft[v] <= ft[u]) || sz % 2) {
            cout << "NO\n";
            continue;
        }
        int c1 = king(st[u], st[v]), c2 = king(ft[v], ft[u]);
        int max_count = max(count(c1, st[u], st[v]) + count(c1, ft[v], ft[u]),
                            count(c2, st[u], st[v]) + count(c2, ft[v], ft[u]));
        // cerr << max_count << endl;
        cout << (max_count * 2 > sz ? "NO\n" : "YES\n");
    }
}

The first step is to realize the solution to a well known dp problem for finding f(A) for a given array. We define dp[i][0] to be the maximum sum for element 1..i where I am allowed to pick element i+1 and dp[i][1] be the maximum sum for element 1...i where I may or may not be allowed to pick i+1 th element. defining such states ensures that dp[i][1]>=dp[i][0] the transition will be such dp[i][0]=dp[i-1][1] and dp[i][1]=max(dp[i][0],dp[i-1][0]+a[i]) where dp[n][1] will be the answer for entire array.

in other words dp[i][1] can use all elements 1....i whereas dp[i][0] can oonly use 1...i-1 elements

Defining it to allow dp[i][1]>=dp[i][0] helps us maintain dp[i][1]-dp[i][0] as one of the states of DP of the original problem where only on basis of the difference we get which elements would be picked in future and sum of dp[i][0] will always be taken in sum out of the excess dp[i][1]-dp[i][0] do we take into account the future dp transitions which is gauranteed to be within the range of just 1 additional element ai which is not allowed in dp[i][0] but is allowed to use in dp[i][1] and hence the difference is within the range of ai<=1e4

SO for the original problems the DP states are ans_dp[i][j] representing that among all subsets/subsequences (total 2^i) of the first i numbers ans_dp[i][j] elements have a differencce between their dp[i][1] and dp[i][0] to be j, note that it is not neccessary that the subsequences have the ith element in them it is just upto i among all subsequences including ai as well as not including ai

to transition from i to i+1 for all subsequences which is not taking a_(i+1) we can directly update for them ans_dp[i+1][j]+=ans_dp[i][j] later as they will have the same difference now considering all subsequces having a_(i+1) in them since dp[i+1][1]=max(dp[i][1],dp[i][0]+a_(i+1)) and dp[i+1][0]=dp[i][1] therefore for all differences j in ans_dp[i][j] where j=dp[i][1]-dp[i][0]>=a_(i+1) will be added to difference j=0 for the next state i+1 and for all j<a_(i+1) we will have gap between for the next state dp[i+1][1]-dp[i+1][0] to be dp[i][0]+a_(i+1)-dp[i][1] =a_(i+1)-j and for all these sequences while storing the gap for the next term we can forget the total common in both dp[i][0] and dp[i][1] by the time we have computed for i we have already added all dp[i][0] terms to the final_answer now for every term we are adding a_(i+1) we should add dp[i][1]-dp[i][0]=j to the final_answer to which n-(i+1) elements remain giving 2^(n-(i+1)) subsequences*j will be added for each of them to the final answer and we have transitioned with remaining gaps for the next as well as adding the answers upto dp[i+1][0] for all numbers.

// In the name of Allah.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14;

vector<int> g[MAX_N];

bool mark[MAX_N];
int par[MAX_N];

void dfs(int v = 0, int p = -1) {
    for (auto u : g[v])
        if (u != p){
            par[u] = v;
            dfs(u, v);
        }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i < n; ++i) {
            int v, u;
            cin >> v >> u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        dfs();
        array cer{0, 0};
        int ans = 1;
        mark[0] = true;
        for (int i = 1; i < n; ++i) {
            if (mark[i]) {
                ++ans;
                continue;
            }
            int v = i;
            while (!mark[v]) {
                mark[v] = true;
                v = par[v];
            }
            auto it = find(cer.begin(), cer.end(), v);
            if (it == cer.end())
                break;
            *it = i;
            ++ans;
        }
        cout << ans << ' ';
        for (int k = 3; k <= n; ++k)
            cout << (k <= g[0].size() + 1) << ' ';
        cout << '\n';
        fill(g, g + n, vector<int>());
        fill(mark, mark + n, false);
    }
}