#include <bits/stdc++.h>
int cl[252], cr[252], sz[252], si[252], su[252];
int dfs0(int u) {
  if (sz[u] != -1) return si[u] = su[u] = 0;
  si[u] = dfs0(cl[u]) ^ dfs0(cr[u]) ^ 1;
  su[u] = su[cl[u]] + su[cr[u]] + 1;
  if (si[cl[u]] > si[cr[u]]) {
    int t = cl[u];
    cl[u] = cr[u];
    cr[u] = t;
  }
  return si[u];
}
int dp[252][3][2];
bool bk[252][3][2];
int add(int a, int b, int c) {
  if (a == -1) return b;
  if (b == -1) return a;
  if (c) return a > b ? a : b;
  return a < b ? a : b;
}
int dfs(int u, int sk, int pa) {
  int a = si[cl[u]] + si[cr[u]];
  if (sz[u] != -1) return sz[u];
  if (su[u] == 1) {
    if (sk == 2) pa ^= 1;
    return add(sz[cl[u]], sz[cr[u]], pa);
  }
  if (bk[u][sk][pa]) return dp[u][sk][pa];
  int rt = -1;
  bk[u][sk][pa] = true;
  if (sk) {
    if (sk == 1) rt = dfs(u, 0, pa ^ 1);
    if (a == 0) {
      if (sz[cl[u]] == -1)
        rt = add(rt,
                 add(dfs(cl[u], 1 + (sk == 1 && sz[cr[u]] != -1), pa),
                     dfs(cr[u], 0, pa ^ 1), pa ^ 1),
                 pa);
      if (sz[cr[u]] == -1)
        rt = add(rt,
                 add(dfs(cl[u], 0, pa ^ 1),
                     dfs(cr[u], 1 + (sk == 1 && sz[cl[u]] != -1), pa), pa ^ 1),
                 pa);
    } else if (a == 1)
      rt = add(dfs(cl[u], 0, pa),
               dfs(cr[u], 1 + (sk == 1 && sz[cl[u]] != -1), pa), pa);
    else
      rt = add(
          add(rt,
              add(dfs(cl[u], 0, pa),
                  dfs(cr[u], 1 + (sk == 1 && su[cl[u]] == 1), pa ^ 1), pa ^ 1),
              pa),
          add(dfs(cl[u], 1 + (sk == 1 && su[cr[u]] == 1), pa ^ 1),
              dfs(cr[u], 0, pa), pa ^ 1),
          pa);
  } else {
    if (a == 0)
      rt = add(dfs(cl[u], 0, pa), dfs(cr[u], 0, pa), pa);
    else if (a == 1) {
      rt = add(dfs(cl[u], 0, pa ^ 1), dfs(cr[u], 0, pa), pa ^ 1);
      rt = add(rt, add(dfs(cl[u], 1, pa), dfs(cr[u], 1, pa ^ 1), pa ^ 1), pa);
    } else
      rt = add(dfs(cl[u], 1, pa), dfs(cr[u], 1, pa), pa);
  }
  return dp[u][sk][pa] = rt;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      scanf("%d", &sz[i]);
      if (sz[i] == -1) scanf("%d%d", &cl[i], &cr[i]);
      for (int a = 0; a < 3; a++) {
        for (int b = 0; b < 2; b++) bk[i][a][b] = false;
      }
    }
    dfs0(0);
    int ans = dfs(0, 0, 1);
    printf("%d\n", ans);
  }
  return 0;
}
