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.
