一只永生的龙袭击了字节大陆。经过数日的战斗，英雄们终于击败了龙。然而，龙是不死的，无法被彻底杀死，因此字节大陆的魔法师们决定使用古老的黑魔法将龙封印。

龙将被封印在一棵包含 $n$ 个顶点的无向魔法树下。树的每个顶点上都有两颗宝石。每颗宝石都有一个魔力值 $m$ 和一个能量值 $p$。黑魔法要求从每个顶点中恰好移除一颗宝石，使得每个顶点恰好剩下一颗宝石。总能量为树中剩余的所有宝石的能量值之和。

为了从封印中逃脱，龙有机会发动攻击。它会选择树上的一个目标顶点，然后选择该顶点及其邻居顶点中的一部分，并对它们发动攻击。如果至少有一个顶点被攻击，且所有被攻击顶点中剩余宝石的魔力值按位异或和等于零，则封印会被破坏，龙就会逃脱。魔法师们绝不能让这种情况发生。

请编写一个程序，帮助他们确定如何选择宝石，使得龙永远无法逃脱，并使总能量最大化。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($2 \le n \le 60$)，表示顶点的数量。

接下来的 $n$ 行中，第 $i$ 行包含四个整数 $m_i, p_i, m'_i$ 和 $p'_i$ ($1 \le m_i, m'_i < 2^{64}$, $1 \le p_i, p'_i \le 10^7$)，描述第 $i$ 个顶点上的两颗宝石。

接下来的 $n - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，描述 $u_i$ 号顶点和 $v_i$ 号顶点之间的一条无向边。

保证输入是一棵树。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示封印龙的总能量。如果无法封印龙，请输出“-1”。

样例

样例输入 1

2
2
3 1 3 1
3 2 3 2
1 2
3
1 3 2 1
2 2 4 3
1 3 3 2
1 2
2 3

样例输出 1

-1
8