Problem Description

Alex has a tree $T$ with $n$ vertices conveniently labeled with $1,2,...,n$. Each vertex of the tree is colored black or white. For every integer pair $(a, b)$, Alex wants to know whether there is a subtree of $T$ with exact $a$ white vertices and $b$ black vertices.

A subtree of $T$ is a subgraph of $T$ that is also a tree.

Input

There are multiple test cases. The first line of input contains an integer $T$ $(1 \le T \le 100)$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ $(1 \le n \le 2000)$. The next line contains a binary string $s$ length $n$ where $s_i$ denoting the color of the $i$-th vertex ('0' means white, while '1' means black). Each of the following $n - 1$ lines contains two integers $a_i, b_i$, denoting an edge between vertices $a_i$ and $b_i$ $(1 \le a_i, b_i \le n)$.

Output

For each test case, output an integer $W = \sum_{a=0}^{n}\sum_{b=0}^{n}{(a+1)(b+1)S(a,b)}$. $S(a,b)=1$ if there is a subtree with exact $a$ white vertices and $b$ black vertices, or $0$ otherwise.

3
4
1010
1 4
2 4
3 4
3
101
1 2
2 3
10
1010111001
1 2
1 3
1 8
2 4
2 6
2 7
3 9
4 5
7 10

33
15
365