Problem: Pieguy and Piegirl are playing a game. They have a rooted binary tree, that has a property that each node is either a leaf or has exactly two children. Each leaf has a number associated with it.

On his/her turn a player can choose any two leafs that share their immediate parent, remove them, and associate either of their values with their parent, that now became a leaf (the player decides which of the two values to associate). The game ends when only one node (the one that was the root of the tree) is left.

Pieguy goes first, and his goal is to maximize the value that will be associated with the root when the game ends. Piegirl wants to minimize that value. Assuming that both players are playing optimally, what number will be associated with the root when the game ends?

Input

First line contains a single integer t (1 ≤ t ≤ 100) — number of test cases. Then t test cases follow. Each test case begins with an empty line, followed by a line with a single integer n (1 ≤ n ≤ 250), followed by n lines describing n nodes of the tree. Each of those n lines either contains a non-negative number ai, indicating a leaf node with value ai (0 ≤ ai ≤ 1000) associated with it, or  - 1 followed by integers l and r, indicating a non-leaf node with children l and r (0 ≤ l, r ≤ n - 1). Nodes are numbered from 0 to n - 1. The root is always node 0.

Output

For each test case print one line with one integer on it — the number that will be associated with the root when the game ends.

Examples

Input

4

3
-1 1 2
10
5

5
-1 1 2
-1 3 4
10
5
20

7
-1 1 2
-1 3 4
-1 5 6
1
2
3
4

11
-1 1 2
-1 3 4
-1 5 6
-1 7 8
15
7
-1 9 10
7
8
9
11


Output

10
10
4
8

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename C>
void ma(C& a, C b) {
  if (a < b) a = b;
}
template <typename C>
void mi(C& a, C b) {
  if (a > b) a = b;
}
int cas, n, l[300], r[300], w[300], roz[300];
void licz_roz(int nr) {
  if (w[nr] == -1) {
    licz_roz(l[nr]);
    licz_roz(r[nr]);
    if (roz[r[nr]] & 1) swap(l[nr], r[nr]);
    roz[nr] = 1 + roz[l[nr]] + roz[r[nr]];
  } else
    roz[nr] = 0;
}
int dp[300][2][3];
int ak[300][2][3];
inline int mima(int a, int b, bool jak) { return ((a > b) ^ jak) ? a : b; }
inline int mima3(int a, int b, int c, bool jak) {
  return mima(mima(a, b, jak), c, jak);
}
int dfs(int nr, bool kto, int pas) {
  if (w[nr] != -1) return w[nr];
  if (roz[nr] == 1) return mima(w[l[nr]], w[r[nr]], kto ^ (pas == 2));
  int& res = dp[nr][kto][pas];
  if (ak[nr][kto][pas] == cas) return res;
  ak[nr][kto][pas] = cas;
  if (pas) {
    if (roz[nr] & 1) {
      res = dfs(nr, !kto, 0);
      if (roz[l[nr]] & 1) {
        int pom =
            mima(dfs(l[nr], kto, 0),
                 dfs(r[nr], !kto, roz[l[nr]] == 1 && pas == 1 ? 2 : 1), !kto);
        res = mima(res, pom, kto);
        pom = mima(dfs(r[nr], kto, 0),
                   dfs(l[nr], !kto, roz[r[nr]] == 1 && pas == 1 ? 2 : 1), !kto);
        res = mima(res, pom, kto);
      } else {
        if (roz[r[nr]]) {
          int pom =
              mima(dfs(l[nr], !kto, 0),
                   dfs(r[nr], kto, roz[l[nr]] == 0 && pas == 1 ? 2 : 1), !kto);
          res = mima(res, pom, kto);
        }
        if (roz[l[nr]]) {
          int pom =
              mima(dfs(r[nr], !kto, 0),
                   dfs(l[nr], kto, roz[r[nr]] == 0 && pas == 1 ? 2 : 1), !kto);
          res = mima(res, pom, kto);
        }
      }
    } else {
      res = mima(dfs(r[nr], kto, 0),
                 dfs(l[nr], kto, roz[r[nr]] == 0 && pas == 1 ? 2 : 1), kto);
    }
  } else {
    if (roz[nr] & 1) {
      if (roz[l[nr]] & 1)
        res = mima(dfs(l[nr], kto, 1), dfs(r[nr], kto, 1), kto);
      else
        res = mima(dfs(l[nr], kto, 0), dfs(r[nr], kto, 0), kto);
    } else {
      int pom = mima(dfs(l[nr], kto, 0), dfs(r[nr], !kto, 0), !kto);
      int pom2 = mima(dfs(l[nr], !kto, 1), dfs(r[nr], kto, 1), !kto);
      res = mima(pom, pom2, kto);
    }
  }
  return res;
}
void tt() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &w[i]);
    if (w[i] == -1) {
      scanf("%d", &l[i]);
      scanf("%d", &r[i]);
    }
  }
  licz_roz(0);
  printf("%d\n", dfs(0, 0, 0));
}
int main() {
  int _;
  scanf("%d", &_);
  for (cas = 1; cas <= _; cas++) tt();
}