给你一个由 $n$ 个顶点和 $m$ 条边组成的无向图。顶点从零开始编号：$0, 1, \dots, n - 1$。你需要处理 $q$ 次询问。每次询问提供一个点对 $(u, v)$，并要求你从图中删除边 $(u, v)$。如果图中不存在这样的一条边（例如，如果 $u = v$），则什么都不做。在每次询问后，输出图是否连通。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 5 \cdot 10^5$），表示测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $q$（$2 \le n \le 10^6$，$1 \le m, q \le 10^6$）：分别表示顶点数、边数和询问数。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$0 \le u_i, v_i < n$），表示 $u_i$ 和 $v_i$ 之间的一条边。图中没有自环，也没有重边。

接下来的 $q$ 行，每行描述一个询问。然而，询问参数 $u_j$ 和 $v_j$ 并不是直接给出的。相反，这些行中的第 $j$ 行包含两个整数 $a_j$ 和 $b_j$（$0 \le a_j, b_j < n$）。假设第 $k$ 次询问的答案为 $c_k$，如果图连通则 $c_k = 1$，否则 $c_k = 0$。那么 $u_j$ 和 $v_j$ 将根据以下公式生成：

$$u_j = (2^{j-2}c_1 + 2^{j-3}c_2 + \dots + 2^1 c_{j-2} + 2^0 c_{j-1} + a_j) \bmod n,$$

$$v_j = (3^{j-2}c_1 + 3^{j-3}c_2 + \dots + 3^1 c_{j-2} + 3^0 c_{j-1} + b_j) \bmod n.$$

所有测试用例中 $n$ 的总和、$m$ 的总和以及 $q$ 的总和均不超过 $10^6$。

输出格式

对于每个测试用例，输出 $q$ 行，包含整数 $c_1, \dots, c_q$：即每次询问的答案。

样例

输入样例 1

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

输出样例 1

0
0
1
1
0
0

说明

在第一个测试用例中，询问要求删除边 $(0, 0)$（该边不存在）和 $(0, 1)$。

在第二个测试用例中，询问要求删除边 $(0, 1)$、$(2, 0)$（该边不存在）、$(3, 0)$ 和 $(0, 3)$（该边已被之前的操作删除）。