O. Sherlock Holmes and the Silent Stakeouts
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Sherlock Holmes is mapping the alleyways of London. The alleyways form a tree rooted at node $$$1$$$ (Baker Street).

Some nodes are crime scenes that must be watched. Holmes can place stakeout teams on some nodes. A team placed at node $$$u$$$ watches every node $$$v$$$ such that:

  • $$$u$$$ is an ancestor of $$$v$$$ in the rooted tree (possibly $$$u=v$$$),
  • and $$$\operatorname{dist}(u,v)\le k$$$, where $$$\operatorname{dist}$$$ is the number of edges on the unique path.

Every crime scene must be watched by at least one team. Your task is to find the minimum number of teams needed.

Important: the list of crime scenes may contain duplicates; a node is a crime scene if it appears at least once.

Input

The first line contains an integer $$$t$$$ ($$$1\le t\le 5$$$) — the number of test cases.

For each test case:

  • The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$1\le m\le n$$$, $$$0\le k\le n$$$) — the number of nodes, the number of crime-scene entries, and the watching distance.
  • The next $$$n-1$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$, $$$u\ne v$$$), describing an undirected edge of the tree.
  • The next line contains $$$m$$$ integers $$$s_1,s_2,\dots,s_m$$$ ($$$1\le s_i\le n$$$) — the crime-scene nodes (possibly with duplicates).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print one integer — the minimum number of stakeout teams needed to watch all crime scenes.

Example
Input
1
8 3 2
1 2
2 4
2 5
1 3
3 6
6 7
6 8
5 7 8
Output
2
Note

In the example, the crime scenes are $$$\{5,7,8\}$$$ and $$$k=2$$$. One optimal strategy is:

  • place a team at node $$$3$$$, which watches nodes $$$3,6,7,8$$$ (all within distance $$$2$$$ downward),
  • place a team at node $$$1$$$, which watches nodes at depth at most $$$2$$$, including node $$$5$$$.
Thus the answer is $$$2$$$.