You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Input

The first line contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases.

The first line of each test case contains three integers $n$, $m$, and $q$ ($2\le n\le 10^5$, $1\le m, q\le 2\cdot 10^5$) — the number of vertices, edges, and queries respectively.

Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1\le u_i, v_i\le n$) — ends of the $i$-th edge.

It is guaranteed that the graph is connected and there are no multiple edges or self-loops.

Each of the next $q$ lines contains two integers $l$ and $r$ ($1\le l\le r\le n$) — descriptions of the queries.

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

Output

For each test case, print $q$ integers — the answers to the queries.

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

0 1 
3 3 0 5 5 
2

Note

Graph from the first test case. The integer near the edge is its number.

In the first test case, the graph contains $2$ vertices and a single edge connecting vertices $1$ and $2$.

In the first query, $l=1$ and $r=1$. It is possible to reach any vertex from itself, so the answer to this query is $0$.

In the second query, $l=1$ and $r=2$. Vertices $1$ and $2$ are reachable from one another using only the first edge, through the path $1 \longleftrightarrow 2$. It is impossible to reach vertex $2$ from vertex $1$ using only the first $0$ edges. So, the answer to this query is $1$.

Graph from the second test case. The integer near the edge is its number.

In the second test case, the graph contains $5$ vertices and $5$ edges.

In the first query, $l=1$ and $r=4$. It is enough to use the first $3$ edges to satisfy the condition from the statement:

• Vertices $1$ and $2$ are reachable from one another through the path $1 \longleftrightarrow 2$ (edge $1$).
• Vertices $1$ and $3$ are reachable from one another through the path $1 \longleftrightarrow 3$ (edge $2$).
• Vertices $1$ and $4$ are reachable from one another through the path $1 \longleftrightarrow 2 \longleftrightarrow 4$ (edges $1$ and $3$).
• Vertices $2$ and $3$ are reachable from one another through the path $2 \longleftrightarrow 1 \longleftrightarrow 3$ (edges $1$ and $2$).
• Vertices $2$ and $4$ are reachable from one another through the path $2 \longleftrightarrow 4$ (edge $3$).
• Vertices $3$ and $4$ are reachable from one another through the path $3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4$ (edges $2$, $1$, and $3$).

If we use less than $3$ of the first edges, then the condition won't be satisfied. For example, it is impossible to reach vertex $4$ from vertex $1$ using only the first $2$ edges. So, the answer to this query is $3$.

In the second query, $l=3$ and $r=4$. Vertices $3$ and $4$ are reachable from one another through the path $3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4$ (edges $2$, $1$, and $3$). If we use any fewer of the first edges, nodes $3$ and $4$ will not be reachable from one another.