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$