Country C is a prosperous nation consisting of $n$ cities and $m$ directed roads, with cities numbered from $1$ to $n$. If one can travel from city $x$ to city $y$ through a sequence of roads, we say that city $x$ can reach city $y$, denoted as $x \Rightarrow y$. The roads in Country C have a special property: for any three cities $x, y, z$, if $x \Rightarrow z$ and $y \Rightarrow z$, then $x \Rightarrow y$ or $y \Rightarrow x$.

In one month, Country C will celebrate its millennium anniversary, and its people are preparing for a grand parade. Currently, Country C has $q$ planned parade routes. The $i$-th parade starts at city $s_i$ and ends at city $t_i$, and during the parade, a city may be visited multiple times. To make the parade more interesting, $k$ ($0 \le k \le 2$) temporary directed roads will be built for each parade, meaning these roads cannot be used by other parade plans.

Country C wants to know how many cities might be visited during each parade plan.

Note: The temporarily built roads do not necessarily satisfy the original property of the roads in Country C.

Input

The input is read from the file celebration.in.

The first line contains four integers $n, m, q, k$, representing the number of cities, the number of roads, the number of parade plans, and the number of temporary roads built for each parade, respectively.

The next $m$ lines each contain two integers $u, v$, representing a directed road $u \to v$.

The next $q$ lines each contain the two integers $s_i, t_i$ representing the start and end cities of each parade; this is followed by $k$ pairs of integers $a, b$, where each pair represents a temporarily added directed road $a \to b$.

It is guaranteed that if the original directed roads of Country C are treated as undirected, all cities are connected.

Output

The output is written to the file celebration.out.

For each query, output a single integer representing the answer. If it is impossible to reach the destination from the starting point, output 0.

Examples

Input 1

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

Output 1

4
4
4
0

Note 1

For the 1st plan, the start is city 1, the end is city 4, and the temporary road is $5 \to 1$. The set of cities that can be visited is $\{1, 2, 4, 5\}$.

For the 2nd plan, the start is city 2, the end is city 3, and the temporary road is $5 \to 3$. The set of cities that can be visited is $\{2, 3, 4, 5\}$.

For the 3rd plan, the start is city 1, the end is city 2, and the temporary road is $5 \to 2$. The set of cities that can be visited is $\{1, 2, 4, 5\}$.

For the 4th plan, the start is city 3, the end is city 4, and the temporary road is $5 \to 1$. It is impossible to reach city 4 from city 3.

Examples

Input 2

See celebration/celebration2.in in the contestant directory. The constraints for this example are the same as test cases 5–7.

Output 2

See celebration/celebration2.ans in the contestant directory.

Input 3

See celebration/celebration3.in in the contestant directory. The constraints for this example are the same as test cases 10–11.

Output 3

See celebration/celebration3.ans in the contestant directory.

Input 4

See celebration/celebration4.in in the contestant directory. The constraints for this example are the same as test cases 15–16.

Output 4

See celebration/celebration4.ans in the contestant directory.

Input 5

See celebration/celebration5.in in the contestant directory. The constraints for this example are the same as test cases 20–25.

Output 5

See celebration/celebration5.ans in the contestant directory.

Constraints

For all test cases, $1 \le n, q \le 3 \times 10^5$, $n - 1 \le m \le 6 \times 10^5$, $0 \le k \le 2$.