Ada the Ladybug and her friends are on trip in Bugraine. Most of them are in different cities at the moment. They want to spread as much as possible, make hologram-skype to show all others the city. They have agreed, to make this call in time T.

The cities are connected with bi-directional roads. Each of the road has some length (which equals to time it takes to travel between two cities).

Input

The first line will contain the number of test-cases.

The first line of each test-case begins with four integers: N, M, F, T, number of cities, number of roads, number of friends (Ada inclusive) and time they have: 1 ≤ N, F ≤ 500, 0 ≤ M ≤ 10⁵, 0 ≤ T ≤ 5*10⁸

Then a line with F integers follows, 1 ≤ H_i ≤ N, the city, where i^th friend currently is.

Afterward M lines follow, with three integers A, B, L, 1 ≤ A, B ≤ N, 1 ≤ L ≤ 10⁶, indicating a road, which connect cities A, B with length of L

PS: There might exist multiple roads between two cities and there might also be a "circular route" which begins and ends in the same city!

Output

For each test-case, print maximal number of different cities Ada and her friends can end up at after T time!

Example Input

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

Example Output

3
5
4

Output Explanation

In first test-case, all 4 friends begin in same node. From this node, one can get to nodes 2 and 5, or stay in the node (in time ≤ 3). Since everyone is in node 1, best they can do is to choose one friend who goes to 5, one who goes to 2 and the rest of them can stay so with "1, 1, 2, 5" they can occupy 3 different nodes (at most).

In second test-case, friends on 6 can go nowhere (just stay in 6). Friends on 2 can go to 3, 4, 5 or stay on 2. So with friends in 6, 6, 2, 3, 4, 5 we get maximum of 5 different cities.

Last (third) test-case is same as first - except for time. This one additional time-unit will let friends go to 4 (or to nodes which they can go in first test-case). "1, 2, 4, 5" would make 4 different cities!