Toy Dog Collection

Bajtazar works at a freight company transporting building materials from the capital city (city 1) to various towns. In Bajtocja, there are \(n\) cities (numbered from 1 to \(n\)) connected by \(n-1\) roads. Each road has a gas station that sells a toy dog. There are \(m\) kinds of toy dogs (numbered from 1 to \(m\)), but each gas station offers only one kind, and the toy dog available at each station may change from day to day.

Every day, Bajtazar drives from the capital (city 1) along the unique shortest path to a destination city \(x\) and then returns along the same path. His son Bitek loves the toy dogs sold at these stations, and Bajtazar wants to know how many different types of toy dogs his son can collect on that day.

Given the configuration of the cities, the gas stations with their current toy dog type, and the destination city \(x\) for a day, determine the number of distinct toy dog types available along the path from city 1 to city \(x\).

inputFormat

The input begins with an integer \(T\) (\(1 \le T\le 10\)) indicating the number of test cases. For each test case:

1. The first line contains two integers \(n\) and \(m\) (\(2 \le n \le 10^5\), \(1 \le m \le 10^5\)), the number of cities and the number of toy dog types respectively.
2. Each of the next \(n-1\) lines contains three integers \(u\), \(v\) and \(t\) (\(1 \le u,v \le n\), \(1 \le t \le m\)), representing a road between cities \(u\) and \(v\) with a gas station selling toy dog of type \(t\).
3. The last line of the test case contains a single integer \(x\) (\(1 \le x \le n\)), the destination city for that day.

It is guaranteed that the given roads form a tree.

outputFormat

For each test case, output a single integer: the number of distinct toy dog types available along the path from city 1 to city \(x\). Note that even though Bajtazar returns by the same path, each gas station is only counted once.

sample

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

2
2
2