#include <bits/stdc++.h>
using namespace std;
int dp[101000][2][3], vis[101000][2][3], n, T, val[101000], sz[101000],
    lc[101000], rc[101000];
void pdfs(int u) {
  sz[u] = 0;
  if (val[u] != -1) return;
  pdfs(lc[u]), pdfs(rc[u]);
  sz[u] = sz[lc[u]] + sz[rc[u]] + 1;
  if (sz[rc[u]] & 1) swap(lc[u], rc[u]);
}
int mer(int a, int b, int p) {
  if (p == 0)
    return max(a, b);
  else
    return min(a, b);
}
int dfs(int u, int nw, int step) {
  if (vis[u][nw][step]) return dp[u][nw][step];
  if (sz[u] == 0) return val[u];
  if (sz[u] == 1) return mer(val[lc[u]], val[rc[u]], nw ^ (step == 2));
  vis[u][nw][step] = 1;
  int v0, v1, va;
  int& ans = dp[u][nw][step];
  if (step == 0) {
    if ((sz[lc[u]] & 1) == 0) {
      ans = mer(dfs(lc[u], nw, 0), dfs(rc[u], nw, 0), nw);
    } else if (sz[rc[u]] & 1) {
      ans = mer(dfs(lc[u], nw, 1), dfs(rc[u], nw, 1), nw);
    } else {
      v0 = mer(dfs(lc[u], nw, 0), dfs(rc[u], nw ^ 1, 0), nw ^ 1);
      v1 = mer(dfs(rc[u], nw, 1), dfs(lc[u], nw ^ 1, 1), nw ^ 1);
      ans = mer(v0, v1, nw);
    }
  } else {
    ans = dfs(u, nw ^ 1, 0);
    if ((sz[lc[u]] & 1) == 0) {
      if (sz[lc[u]]) {
        v0 = dfs(lc[u], nw, 1 + (sz[rc[u]] == 0 && step == 1));
        v1 = dfs(rc[u], nw ^ 1, 0);
        ans = mer(ans, mer(v0, v1, nw ^ 1), nw);
      }
      if (sz[rc[u]]) {
        v0 = dfs(rc[u], nw, 1 + (sz[lc[u]] == 0 && step == 1));
        v1 = dfs(lc[u], nw ^ 1, 0);
        ans = mer(ans, mer(v0, v1, nw ^ 1), nw);
      }
    } else if (sz[rc[u]] & 1) {
      v0 = dfs(lc[u], nw ^ 1, 1 + (sz[rc[u]] == 1 && step == 1));
      v1 = dfs(rc[u], nw, 0);
      ans = mer(ans, mer(v0, v1, nw ^ 1), nw);
      v0 = dfs(rc[u], nw ^ 1, 1 + (sz[lc[u]] == 1 && step == 1));
      v1 = dfs(lc[u], nw, 0);
      ans = mer(ans, mer(v0, v1, nw ^ 1), nw);
    } else {
      v0 = dfs(lc[u], nw, 1 + (sz[rc[u]] == 0 && step == 1));
      v1 = dfs(rc[u], nw, 0);
      ans = mer(ans, mer(v0, v1, nw), nw);
    }
  }
  return ans;
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    for (int i = 0; i <= n; ++i) lc[i] = sz[i] = rc[i] = 0;
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 3; ++k) vis[i][j][k] = 0;
    for (int i = 0; i < n; ++i) {
      scanf("%d", &val[i]);
      if (val[i] == -1) scanf("%d%d", &lc[i], &rc[i]);
    }
    pdfs(0);
    printf("%d\n", dfs(0, 0, 0));
  }
}
