Problem Description

Ben works as an engineer in a city with $N$ electric junctions. These junctions form a network and can be visualised as a connected graph with $N$ vertices and $N-1$ edges. The city is facing a power outage, due to which none of the junctions are receiving electricity, and Ben is in charge of handling the situation.

Each junction has a fixed electric capacity. $A_i$ is the electric capacity of the $i$-th junction. Due to resource constraints, Ben can provide electricity to only one junction, but other junctions can receive electricity depending on their connections and capacities. If the $i$-th junction receives electricity, then it will also get transmitted to all the junctions directly connected to the $i$-th junction whose capacity is strictly less than $A_i$. Transmission stops if no eligible junction is present. Help Ben determine the maximum number of junctions that can receive electricity.

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains an integer $N$ which represents the number of junctions in the city.

The next line contains $N$ integers. The $i$-th integer is $A_i$, which is the electric capacity of the $i$-th junction.

The next $N-1$ lines each contain two integers $X_i$ and $Y_i$, meaning that the junctions $X_i$ and $Y_i$ are directly connected to each other.

Output Format

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the maximum number of junctions that can receive electricity.

2
5
1 2 3 4 3
1 3
2 3
4 3
4 5
6
1 2 3 3 1 4
3 1
3 2
3 4
4 5
1 6

Case #1: 5
Case #2: 3

Hint

:::align{center} :::

In Sample Case #1, the optimal solution is to provide electricity to the fourth junction. This will transmit electricity to all the junctions eventually.

If the electricity is provided to the third junction, it will transmit it to the first and second junction, but not to the fourth junction. In that case, only three junctions can finally receive electricity.

:::align{center} :::

In Sample Case #2, the optimal solution is to provide electricity to the third junction. This will transmit it to the first and second junctions. Note that electricity will not be transmitted to the fourth junction, since its capacity is not strictly less than that of the third junction.

If electricity is provided to the sixth junction, it will only be transmitted to the first junction.

If electricity is provided to the fourth junction, it will only be transmitted to the fifth junction.

Limits

$1 \le T \le 100.$

$1 \le A_i \le 10^9$, for all $i$.

$1 \le X_i, Y_i \le N$, for all $i$.

All the junctions are part of a single connected network.

Test Set $1$

$1 \le N \le 10^3.$

Test Set $2$

For at most $15$ cases:

$1 \le N \le 2 \times 10^5.$

For the remaining cases:

$1 \le N \le 10^3.$