F. Простая задача о деревьях
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Pieguy и Piegirl играют в игру. У них есть корневое бинарное дерево, которое обладает следующим свойством: каждая вершина дерева либо лист, либо имеет ровно два сына. Каждый лист имеет некоторое значение, ассоциированное с ним.

Во время игры игроки по очереди делают ходы. На своем ходу игрок выбирает два листа, имеющих общего непосредственного предка, и удаляет их. При этом он ассоциирует с общим предком листов (после удаления он станет листом) какое-то одно из ассоциированных с ними значений на свой выбор. Игра заканчивается, когда в дереве остается ровно одна вершина — корень дерева.

Pieguy ходит первым и его цель — максимизировать значение, которое будет ассоциировано с корнем в конце игры. Piegirl, наоборот, хочет минимизировать это значение. Считая, что оба игрока играют оптимально, вычислите значение, которое будет ассоциировано с корнем в конце игры.

Входные данные

В первой строке записано целое число t (1 ≤ t ≤ 100) — количество тестовых данных. Далее идет описание t тестовых данных. Каждый тест начинается с пустой строки, за которой следует строка, содержащая целое число n (1 ≤ n ≤ 250) — количество вершин дерева. Затем следуют n строк, описывающих n вершин дерева. Если текущая строка описывает лист дерева, то в ней содержится одно неотрицательное целое число ai (0 ≤ ai ≤ 1000), обозначающее ассоциированное с этим листом значение. Иначе, сперва в строке записано число  - 1, а затем два целых числа l и r (0 ≤ l, r ≤ n - 1) — номер левого и правого сыновей текущей вершины. Вершины дерева пронумерованы от 0 до n - 1. Корень дерева — это вершина с номером 0.

Выходные данные

Для каждого теста в отдельной строке выведите ответ на задачу.

Примеры
Входные данные
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
Выходные данные
10
10
4
8