Pieguy 和 Piegirl 正在玩游戏。它们有一个有根二叉树,其属性是每个节点要么是叶子,要么恰好有两个子节点。每片叶子都有一个与之相关的编号。
在他/她的回合中,玩家可以选择任何两个共享其直接父级的叶子,删除它们,并将它们的值与现在成为叶子的父级关联起来(玩家决定关联两个值中的哪一个)。当只剩下一个节点(即树的根节点)时,游戏结束。
Pieguy 先走,他的目标是在游戏结束时最大化与根相关的值。 Piegirl 希望最小化该值。假设两个玩家都处于最佳状态,那么当游戏结束时,与根相关联的数字是多少?
输入
第一行包含一个整数 t (1 ≤ t ≤ 100) — 测试用例的数量。然后是测试用例。每个测试用例以一个空行开始,后面跟着一行包含单个整数 n (1 ≤ n ≤ 250) 的行,然后是描述树的 n 个节点的 n 行。这 n 行中的每一行要么包含一个非负数 ai,指示与其关联的值 ai (0 ≤ ai ≤ 1000) 的叶节点,要么包含 - 1 后跟整数 l 和 r,指示具有子节点 l 和 r (0 ≤ l, r ≤ n - 1) 的非叶节点。节点编号从 0 到 n-1。根始终是节点 0。
输出
对于每个测试用例,打印一行,上面有一个整数——游戏结束时与根相关联的数字。
示例
输入 #1
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
输出 #1
10 10 4 8