Description

给定 $n$ 个顶点的树 $T$，第 $i$ 个点的点权为 $a_i$；设二元函数 $f(u,v)$ 表示树上的两个顶点 $u,v\in T$ 之间（包含 $u,v$）的简单路径\footnote{树上简单路径: 即由顶点序列 $v_0, v_1, v_2, \dots, v_k$ 构成的路径中，所有顶点 $v_0, v_1, \dots, v_k$ 互不相同（$i \neq j \implies v_i \neq v_j$）。}上所有点权的异或和\footnote{异或和: 将一组数通过依次按位异或的结果，具体表示为 $v_0\oplus v_1\oplus v_2\oplus \cdots \oplus v_k$。}。

设三元函数 $g(u,v,w) = f(u,v)\oplus f(v,w)\oplus f(u,w)$，显然函数 $g$ 中的三个参数满足交换律，所以你只需要找出有多少个无序三元组 $\{ u,v,w \}$ 满足 $g(u,v,w) = 0$，并将此结果对 $998244353$ 模取后输出。

Format

Input

本题包含多个测试数据，第一行包含一个整数 $T$ 满足 $1\leq T\leq 1\times 10^4$，表示测试数据组数。

对于每一组测试数据，第一行一个整数 $n$ 满足 $3\leq n\leq 2\times 10^5$ 表示树的顶点数量。

每组测试数据的第二行 $n$ 个整数，其中第 $i$ 个数字表示为 $a_i$ 满足 $0\leq a_i\leq 1\times 10^6$ 表示每个顶点的权值。

接下来的 $n-1$ 行，每一行包含两个整数 $u,v$ 满足 $1\leq u,v\leq n$，表示在 $a_u$ 顶点和 $a_v$ 顶点之间建立无向边。保证给出的 $u,v$ 对一定可以构成一棵树。

保证所有测试数据的 $n$ 的总和不超过 $2\times 10^5$。

Output

输出共 $T$ 行，每行输出一个整数，表示在该树上无序三元组 $\{ u,v,w \}$ 满足 $g(u,v,w) = 0$ 对 $998244353$ 取模的个数。

Samples

1
12
0 4 2 6 9 0 8 5 2 1 3 2
1 2
1 3
2 4
2 5
3 6
3 7
3 8
6 9
6 10
6 11
8 12

76

Note

对于第三组样例，其示意图如下：

一个满足条件的三元组为 $\{ 4,8,1 \}$，其中

1. $f(4,8) = 6\oplus 4 \oplus 0 \oplus 2 \oplus 5 = 5$
2. $f(8,1) = 5\oplus 2 \oplus 0 = 7$
3. $f(1,4) = 0 \oplus 4 \oplus 6 = 2$

最后可得 $g(4,8,1) = f(4,8)\oplus f(8,1)\oplus f(1,4) = 5\oplus 7\oplus 2 = 0$