P14654 夤生月

 我曾坠入三层梦境，梦中来到这片山谷。 山谷中生长着一片彼岸花，如赤红的火，烧向天边。 是对迷惘者的告诫，再往前，即是死亡的高崖。 >「在期待般拒绝出口之前 > > $\;$轻轻啃噬便足以隔绝这语言 > > $\;$透明晚霞般的红又再现 > > $\;$自眼睑到颤抖指尖」 我点燃烈火烧尽一切，一片死寂、空洞。 待灰烬散去，唯记夤夜青灯，梦里人间。 >「请点燃我心的灼之花 > > $\;$让灰烬肆意飘洒 > > $\;$微弱的光能否映亮你的脸颊 > > $\;$若是从未启程的故事 > >$\;$能够有结局的话 > >$\;$残留枯枝也会绽放吧$\;$」

小 L 给你出了一道简单数学题。 对于一个长度为 $n$ 的排列 $p_n$，我们在 $i$ 与 $p_i$ 之间连无向边，设形成的连通块个数为 $C(p_n)$。 对于一个连通块 $S$，如果他包含的点的编号为 $x_1,x_2\dots x_k$，那么他的权值为 $w(S)=\sum\limits_{i=1}^k 2^{x_i}$。 如果连通块分别为 $S_1,S_2\dots S_{C(p_n)}$，那么记该排列的权值为 $\sum\limits_{i=1}^{C(p_n)}2^{w(S_i)}$。 记 $F(n,m)$ 表示 $C(p_n)=m$ 的 $p_n$ 个数。 记 $G(n,m)$ 为 $C(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\%$ 的数据，$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$。