CFCF2178G.deCH OR Dations

由于北极的供应链出现了问题（据说是一个懒惰的小精灵惹的祸），圣诞老人计划在今年圣诞节送出手绘的圆形作为礼物。请你帮他装饰这些圆形！

在圆周上有 $2n$ 个等间距的点，顺时针标记为 $1,2,\ldots,2n$。圣诞老人选择了 $n$ 条端点互不相同的弦，第 $i$ 条弦连接点 $a_i$ 和 $b_i$。他将依次把这些弦绘制到圆上。

当圣诞老人画完前 $\ell$ 条弦后，考虑这 $\ell$ 条弦的任何非空子集 $S$，设 $1\leq c_1<c_2<\cdots<c_{|S|}\leq \ell$ 为其编号。如果对于所有 $1\leq k < |S|$，弦 $c_k$ 与弦 $c_{k+1}$ 都相交，则称 $S$ 为一条“链”。注意，如果 $|S|=1$，则 $S$ 总是一条链。

圣诞老人不希望有哪条弦“格格不入”。因此，只有当每条弦在所有子链中出现偶数次时，才认为这些弦是“紧密联系的”。

对于每个 $\ell = 1$ 到 $n$，请你帮圣诞老人判断这前 $\ell$ 条弦是否紧密联系。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数。

每个测试用例的第一行为一个整数 $n$（$2\le n\le 5\cdot 10^5$）——表示弦的数量。

接下来 $n$ 行，每行两个整数 $a_i$ 和 $b_i$（$1\le a_i<b_i\le 2n$），表示第 $i$ 条弦的两个端点。

保证所有端点均不同。

保证所有测试用例的 $n$ 之和不超过 $5\cdot 10^5$。

对于每个测试用例，输出一个长度为 $n$ 的字符串，第 $\ell$ 个字符为 $\mathtt{1}$ 当且仅当前 $\ell$ 条弦是紧密联系的，否则为 $\mathtt{0}$。

在第一个测试用例中，没有任意两条弦相交，因此每条弦都只会出现在唯一一条以自身为链的链中。因此对于所有 $\ell$，这些弦都不是紧密联系的。

在第二个测试用例中，以下分别是在画完前 $\ell=1,2,3,4$ 条弦之后的示意图与解释。弦的编号集合用表示对应组合的下标集合。

说明 示意图 链

• $\{1\}$。

出现情况

• 弦 $1$ 仅出现在 $1$ 条链中。

说明

• 由于弦 $1$ 出现了奇数次，这些弦不是紧密联系的。
• 注意，包含单条弦的集合总是链。

链

• $\{1\}$、$\{1,2\}$、和 $\{2\}$。

出现情况

• 弦 $1$ 出现了 $2$ 次；
• 弦 $2$ 出现了 $2$ 次。

说明

• 每条弦都出现了偶数次，这些弦是紧密联系的。

链

• $\{1\}$、$\{1,2\}$、$\{2\}$、$\{3\}$。

出现情况

• 弦 $1$ 出现 $2$ 次；
• 弦 $2$ 出现 $2$ 次；
• 弦 $3$ 出现 $1$ 次。

说明

• 弦 $3$ 仅出现了奇数条链中，因此不是紧密联系的。

链

• $\{1\}$、$\{1,2\}$、$\{1,2,4\}$、$\{2\}$、$\{2,4\}$、$\{3\}$、$\{3,4\}$、和 $\{4\}$。

出现情况

• 弦 $1$ 出现 $3$ 次；
• 弦 $2$ 出现 $4$ 次；
• 弦 $3$ 出现 $2$ 次；
• 弦 $4$ 出现 $4$ 次。

说明

• 弦 $1$ 只出现了奇数次，所以不是紧密联系的。
• 需要注意，$\{2,3,4\}$ 并不是链，因为弦 $2$ 与弦 $3$ 不相交。

所以应该输出 $\mathtt{0100}$。