There are $N$ towns in Heung Shing numbered $1$ to $N$. After hosting a very successful Night Vibes Heung Shing event (Heung Shing Yeah Bun Fun), the government has enough funding to set up $M$ bus routes between pairs of towns. For each bus route connecting towns $A$ and $B$ ($A \neq B$ guaranteed), a new bus stop will be set up in $A$ and another in $B$. So if a town is connected by $K$ bus routes, there will be $K$ bus stops set up in that town.

Now, you need to answer $Q$ questions of the form: how many bus stops will be built in towns $X, X + 1, \cdots, Y - 1, Y$ in total?

Input

The first line contains three integers $N, M$ and $Q$.
The next $M$ lines contain two integers $A$ and $B$, specifying the towns connected by each road.
The next $Q$ lines contain two integers $X$ and $Y$ specifying each question.

Output

For each query, output the number of required bus stops on a new line.

Constraints

For all cases, $2 \le N \le 10^6$ and $1 \le M, Q \le 10^6$.
Subtask 1 (20%): $N, M, Q \le 10^3$
Subtask 2 (80%): No additional constraints