An immortal dragon attacked the Byteland. After days of battle, the heroes finally beat the dragon. However, the dragon is immortal such that it can not be killed, so the magicians in Byteland decide to seal the dragon using ancient black magic.
The dragon is scheduled to be sealed under an undirected magic tree with n vertices. In each vertice of the tree, there are two gems. Each gem has its magic value m and power value p. The black magic requires removing exactly one gem from each vertex such that there will be exactly one gem remaining at each vertex. The total power is the sum of the power values of all the gems that remained in the tree.
To escape from sealed, the dragon has a chance to attack. It will choose a target vertex on the tree, then select some vertices among it and its neighbor vertices, and finally start an attack on them. If at least one vertex is attacked, and the bitwise XOR sum among magic values of all the gems in attacked vertices is equal to zero, the tree will be broken, and the dragon escapes. The magicians must never let this happen.
Please write a program to help them determine how to choose gems such that the dragon can never escape, and the total power is maximized.
The first line contains a single integer T (1≤T≤10), the number of test cases. For each test case:
The first line contains a single integer n (2≤n≤60), denoting the number of vertices.
In the next n lines, the i-th line contains four integers mi, pi, mi′ and pi′ (1≤mi,mi′<264, 1≤pi,pi′≤107), describing the two gems in the i-th vertex.
Each of the following n−1 lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), describing an undirected edge between the ui-th vertex and the vi-th vertex.
It is guarenteed that the input is a tree.
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
8