#626 Paths with Equal Ends

Statement

Statement language

You are given a tree with $N$ vertices numbered from $1$ to $N$ . Vertex $i$ has a positive integer $A_i$ written on it.

If two vertices $u,v$ have equal values, that is, $A_u=A_v$ , you may choose the path between $u$ and in the tree. The chosen path contains both endpoints and every vertex between them.

Only the endpoint values must be equal; the values at internal vertices may be anything. For example, if the tree is $1-2-3$ and its values are $(7,1,7)$ , you may choose the path $1-2-3$ containing all three vertices.

You may also choose the same vertex as both endpoints. Such a path consists of just that vertex.

Choose paths satisfying both of the following conditions.

Different paths have no vertex in common, including their endpoints.
Every vertex belongs to exactly one chosen path.

You do not have to use every edge. Paths follow the original edges of the tree; choosing a path does not add a new edge.

Find the minimum number of paths needed. A valid choice always exists by choosing a separate single-vertex path for each vertex.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum number of paths on its own line.

Constraints

$1\leq T\leq200\ 000$ .
$1\leq N\leq200\ 000$ .
$1 \leq A_{i}$ ().

Subtasks

#	Score	Constraints
1	6	In each test case, $N\leq10$ . The sum of $N$ over all test cases is at most $1000$ .
2	9	$U_i=1$ , ().

Samples

Sample 1

Input

Output

1
2
1

In the first case, the single path $1-2-3$ covers every vertex. Both endpoint values are $7$ ; the internal value $1$ does not matter. In the second case, choose path $2-1-3$ and the single-vertex path . They are vertex-disjoint and each has equal endpoint values. One path cannot cover all vertices, so the answer is . In the third case, the only vertex forms one path.