#include <bits/stdc++.h>

#define FASTER() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(), a.end()
#define dbg(x) cerr<<" "<<#x<<" "<<x<<endl

typedef long long ll;

using namespace std;

int root = -1;

void root_find(int v, int p, vector <vector <int>> &gr, vector <int> &cost) {
    if(gr[v].size() == 0 && cost[v] == -1) {
        root = v;
        return;
    }
    for(auto to : gr[v]) {
        if(to != p) {
            root_find(to, v, gr, cost);
        }
    }
}

bool swap_needed(pair <int, int> &l, pair <int, int> &r) {
    if(l.ff > r.ss) {
        return true;
    }
    if(l.ff == r.ss) {
        if(l.ff > r.ss) return true;
    }
    return false;
}

pair <int, pair <int, int>> get(int v, vector <int> &left, vector <int> &right, vector <int> &cost) {
    if(cost[v] != -1) {
        return {0, {cost[v], cost[v]}};
    }
    auto l = get(left[v], left, right, cost),
        r = get(right[v], left, right, cost);
    int sum = l.ff + r.ff;
    if(swap_needed(l.ss, r.ss)) {
        swap(l.ss, r.ss);
        sum++;
    }
    pair <int, int> tmp = {l.ss.ff, r.ss.ff};
    return {sum, tmp};
}

void solve() {
    int n;
    cin >> n;
    vector <int> left(n, -1), right(n, -1);
    vector <int> cost(n, -1);
    vector <vector <int>> revgr(n);
    int leaf = -1;
    for(int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        if(l == -1) {
            cost[i] = r;
            leaf = i;
        } else {
            l--; r--;
            revgr[l].pb(i);
            revgr[r].pb(i);
            left[i] = l;
            right[i] = r;
        }
    }
//    root_find(leaf, -1, revgr, cost);
    auto ans = get(0, left, right, cost);
    dbg(ans.ss.ff); dbg(ans.ss.ss);
    cout << ans.ff <<  '\n';
}

int main() {
    FASTER();
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}