Ada the Ladybug lives on a bush. A typical bush consists of some fruits connected with branches. Ada wants to travel between some fruits. Problem is that each edge can stand only some X_i weight (so if some creature with more weight would like to travel over the edge, it would break and the creature would fall of the bush).

Ada wants to make several travels so she asks you (for each such travel) to how many distinct fruits she can get?

Input

The first line of each test-case will contain three integers 2 ≤ N ≤ 10⁵, the number of fruits, 1 ≤ M ≤ 2*10⁵, the number of edges and 1 ≤ Q ≤ 3*10⁵, the number of queries.

The next M lines will contain three integers 0 ≤ a, b < N (a ≠ b), the fruits which are connected by and edge and 1 ≤ X_i ≤ 10⁵.

The next Q lines will contain two integers 0 ≤ a < N, the fruit Ada starts in and 1 ≤ Y ≤ 10⁵, her actual weight.

NOTE Multiedges are allowed.

Output

For each query, output the number of fruits Ada can get to.

Example Input

4 4 3
1 2 4
2 3 3
3 0 4
0 1 3
1 3
1 4
1 5

Example Output

4
2
1

Example Input

8 10 8
1 3 3
1 2 2 
3 5 1
3 4 3
2 4 7
5 6 2
4 6 8
4 7 3
7 0 1
6 0 4
1 3
1 4
0 5
6 6
6 1
2 3
0 4
5 2

Example Output

7
1
1
3
8
7
4
8