There are $n$ cities and $n - 1$ roads in Byteland, and they form a tree. The cities are numbered $1$ through $n$. The population in $i$-th city is $p_i$.
Soda, the king of Byteland, wants to travel from a city $u$ to another city $v$ along the shortest path. Soda would be happy if the difference between the maximum and minimum population among the cities passed is **no larger than** $D$. So, your task is to tell Soda how many different pairs $(u, v)$ that can make him happy.
Input
There are multiple test cases. The first line of input contains an integer $T$ $(1 \le T \le 500)$, indicating the number of test cases. For each test case:
The first line contains two integers $n$ and $D$ $(1 \le n \le 100000, 1 \le D \le 10^9)$.
The second line contains $n$ integers $p_1, p_2, ..., p_n$ $(0 \le p_i \le 10^9)$.
Each of the following $n - 1$ lines describing roads contains two integers $u, v$ $(1 \le u, v \le n, u \ne v)$ meaning that there is a road connecting city $u$ and city $v$.
It is guaranteed that the total number of vertices in the input doesn't exceed $5 \times 10^5$.
Output
For each test case, output the number of different pairs that can make Soda happy.
Sample Input
1
3 3
1 2 3
1 2
2 3
Sample Output
6
Hint
If you need a larger stack size,
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.
