Marks :15

: 12 | : 1

You are given the following:

- A Tree with $$$n$$$ nodes
- An array $$$A$$$ denoting the value of each node

- All nodes in the path are traversed exactly once.
- The value of starting node and terminating node in the path is same and $$$starting \hspace{3pt} node \neq terminating \hspace{3pt} node$$$.
- The values of any node in the path are not greater than the value of starting node.

Count the number of special paths in the tree.

Note: Two paths are different if they contain at least one different node.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The description of $$$t$$$ testcase follows.

The first line of each test case contains a single integer $$$n$$$ — the number of vertices in the tree $$$(2 \le n \le 10^5)$$$.

The second line contains $$$n$$$ space separated integers $$$a_1,a_2,...a_n$$$ $$$(1 \le a_i \le 10^9)$$$ denoting the values of the nodes of the tree.

The next $$$n-1$$$ lines describe the tree. Each contains two space separated integers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le n; $$$ $$$u \neq v \hspace{1 pt};)$$$ denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that these edges form a tree.

It is guaranteed that the sums of $$$n$$$ and $$$q$$$ over all test cases do not exceed $$$10^5$$$ individually.

Output

For each test case, print the count of special paths in the tree in a new line.

Example

Input

452 3 1 2 31 21 33 43 562 3 1 2 3 31 21 33 43 52 653 3 2 3 32 13 24 25 351 3 1 2 32 13 14 15 1

Output

2 4 6 2

Note

In sample test case 1, The following paths are special paths:

- Path $$$1(2)\to 3(1)\to 4(2)$$$
- Path $$$2(3)\to 1(2)\to 3(1)\to 5(3)$$$

In sample test case 2, The following paths are special paths:

- Path $$$1(2) \to 3(1) \to 4(2)$$$
- Path $$$2(3) \to 1(2) \to 3(1) \to 5(3)$$$
- Path $$$6(3) \to 2(3)$$$
- Path $$$6(3) \to 2(3) \to 1(2) \to 3(1) \to 5(3)$$$

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Successful

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

But to **Run** or **Submit** the Problem, you need to Log In.

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Do let us know your issue.