Mr. Hamra is preparing a crazy experiment for the next scientific Saturday.
Quantum entanglement is a weird relationship that can occur between two particles. And it has the following feature: if particles $A$ and $B$ are in quantum entanglement, and $B$ and $C$ are in quantum entanglement, then $A$ and $C$ are in quantum entanglement too.
Mr. Hamra has $N$ particles. He knows $M$ relationship of quantum entanglement between them. For his magical experiment, he will ask you $Q$ questions, in each question he will give you two particles and ask whether there is a quantum entanglement between them.
First line of the input will be $T$, the number of test cases.
Each test case starts with a line of three numbers, $N, M, Q$ ($1 <= N, M, Q <= 10^5$) the number of particles, quantum entanglement between particles, and the number of questions.
each of the next $M$ lines contain two integers, $u$ and $v$ the particles that are in quantum entanglement.
Next $Q$ lines contain two integers, $X$ and $Y$ the $i_{t h}$ questions.
For each test case, print a binary string of length $Q$ the $i_{t h}$ char of the string is "1" if there is a quantum entanglement between them or "0" otherwise (Without the quotes).
## Input
First line of the input will be $T$, the number of test cases.Each test case starts with a line of three numbers, $N, M, Q$ ($1 <= N, M, Q <= 10^5$) the number of particles, quantum entanglement between particles, and the number of questions.each of the next $M$ lines contain two integers, $u$ and $v$ the particles that are in quantum entanglement.Next $Q$ lines contain two integers, $X$ and $Y$ the $i_{t h}$ questions.
## Output
For each test case, print a binary string of length $Q$ the $i_(t h)$ char of the string is "1" if there is a quantum entanglement between them or "0" otherwise (Without the quotes).
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ N, M, Q \in \mathbb{Z} $ denote the number of particles, entanglement relations, and queries, respectively.
- Let $ G = (V, E) $ be an undirected graph where $ V = \{1, 2, \dots, N\} $ is the set of particles, and $ E \subseteq V \times V $ is the set of $ M $ entanglement edges.
- The entanglement relation is transitive: if $ (u,v) \in E $ and $ (v,w) \in E $, then $ u $ and $ w $ are in the same connected component.
**Constraints**
1. $ 1 \le T \le \text{unspecified} $
2. For each test case:
- $ 1 \le N, M, Q \le 10^5 $
- For each edge $ (u,v) \in E $: $ 1 \le u, v \le N $, $ u \ne v $
- For each query $ (X,Y) $: $ 1 \le X, Y \le N $
**Objective**
For each test case, compute the connected components of $ G $.
For each query $ (X,Y) $, output:
$$
\begin{cases}
\texttt{"1"} & \text{if } X \text{ and } Y \text{ are in the same connected component} \\
\texttt{"0"} & \text{otherwise}
\end{cases}
$$
Output a binary string of length $ Q $ for each test case.