You are given a tree $$G$$ with $$N$$ nodes. The $$i^{th}$$ node of the tree has been assigned value $$A_i$$. We define $$d(u, v)$$ as the bitwise xor of weight of nodes present on the simple path between $$u$$ and $$v$$. You are required to find:
$$
\sum\limits_{i=1}^{N} \sum\limits_{j=i+1}^{N} d(i,j)
$$

Input format

• The first line contains a single integer $$T$$ denoting the number of test cases.
• The first line of each test case contains an integer $$N$$ that denotes the number of nodes in tree $$G$$.
• The second line of each test case contains $$N$$ space-separated integers denoting the initial weight on the nodes of the tree($$A_i$$).
• For each test case, $$(N-1)$$ lines follow. Each of these lines contains two space-separated integers $$u$$ and $$v$$ denoting that there is an edge between these two nodes.

Output format

For each test case(in a separate line), output the sum $$ \sum\limits_{i=1}^{N} \sum\limits_{j=i+1}^{N} d(i,j) $$, where $$d(i, j)$$ is the bitwise xor of weight of nodes present on the simple path between $$i$$ and $$j$$.

Constraints

$$ 1 \le T \le 1000 \\
1 \le N \le 10^5 \\
1 \le A_i \le 10^9 \\
\text{Sum of N over all test cases does not exceed } 10^6 $$