You are given an undirected tree $G$ with $N$ nodes. You are also given an array $A$ of $N$ integer elements where $A[i]$ represents the value assigned to node $i$ and an integer $K$.

You can apply the given operation on the tree at most once:

• Select a node $x$ in the tree and consider it as the root of the tree.
• Select a node $y$ in the tree and update the value of each node in the subtree of $y$ by taking its XOR with $K$. That is, for each node $u$ in the subtree of node $y$, set $A[u] = A[u] XOR K$.

Find the maximum sum of values of nodes that are available in the tree, after the above operation is used optimally.

Note

• Assume 1-based indexing.
• XOR represents the bitwise XOR operator. 

Input format

• The first line contains a single integer $T$ that denotes the number of test cases.
• For each test case:
  • The first line contains an integer $N$.
  • The second line contains an integer $K$.
  • The third line contains $N$ space-separated integers denoting array $A$.
  • Next $N - 1$ lines contain two space-separated integers denoting an edge between node $u$ and $v$.

Output format

For each test case, print the maximum possible sum of values of nodes present in the tree. Print the output for each test case in a new line.

Constraints

$1 \le T \le 10 \\ 1 \le N \le 10^5 \\ 0 \le A[i] \le 10^9 \\ 0 \le K \le 10^9$