题目描述

小 L 给你出了一道简单数学题。

对于一个长度为 $n$ 的排列 $p_n$，我们在 $i$ 与 $p_i$ 之间连无向边，设形成的连通块个数为 $R(p_n)$。

对于一个连通块 $S$，如果他包含的点的编号为 $x_1,x_2\dots x_k$，那么他的权值为 $val(S)=\sum\limits_{i=1}^k 2^{x_i}$。

如果连通块分别为 $S_1,S_2\dots S_{R(p_n)}，那么$记该排列的权值为 $\sum\limits_{i=1}^{R(p_n)}2^{val(S_i)}$。

记 $F(n,m)$ 表示 $R(p_n)=m$ 的 $p_n$ 个数。

记 $G(n,m)$ 为 $R(p_n)=m$ 的 $p_n$ 的不同权值数量。

这里认为 $F(0,0)=G(0,0)=1$。

现在有 $Q$ 次询问，每次给出 $op,n,m$：

• 如果 $op=1$，你需要输出 $F(n,m)\bmod 2$。
• 如果 $op=2$，你需要输出 $G(n,m)\bmod 2$。

输入格式

第一行一个整数 $Q$ 代表询问次数。

接下来 $Q$ 行，每行三个整数 $op,n,m$ 代表小 L 的一次询问。

• 如果 $op=1$，你需要输出 $F(n,m)\bmod 2$。
• 如果 $op=2$，你需要输出 $G(n,m)\bmod 2$。

输出格式

一行一个长度为 $Q$ 的 $01$ 字符串代表答案序列。

20
1 3 8
2 10 2
2 8 2
1 3 1
2 3 3
1 1 5
1 5 10
2 9 8
1 9 5
2 6 6
2 1 0
2 6 4
1 5 3
1 2 5
2 4 7
2 0 2
2 0 5
2 8 1
2 7 1
1 8 8

01101000110110000111

提示

• 对于 $20\%$ 的数据，$0\leq n,m\leq 10$。
• 对于 $40\%$ 的数据，$0\leq n,m\leq 5000$。
• 对于另外 $15\%$ 的数据，$op=1$。
• 对于另外 $15\%$ 的数据，$op=2$。
• 对于另外 $15\%$ 的数据，$0\leq n,m\leq 10^5$。
• 对于 $100\%$ 的数据，$1\leq Q\leq 10^6,0\leq n,m\leq 10^9,1\leq op\leq 2$。