题目背景

小 C 拉小 L 去见岳父岳母。

岳父岳母决定考验小 L 的智商，于是他们出了一道题。

题目描述

岳父给定一个下标从 $1$ 开始的数组 $a$，初始时 $a_i = 2^{i-1}$。

岳母让小 L 对这个数组进行如下操作若干次：

第 $i$ 次操作中，选择两个数 $u_i,v_i\ (2 \le u_i<v_i)$，依次执行：

• $a_{v_i} \gets a_{v_i}+a_{u_i}+a_{u_i-1}$

• $a_{u_i} \gets -\infty$

• $a_{u_i-1} \gets -\infty$

对于第一次操作没有特殊限制，但对于之后的每一次操作，都必须保证 $v_i > v_{i-1}$。

给出 $T$ 次询问，每次两个数 $k$ 和 $x$，请回答能否通过有限次操作，使 $a_k = x$。

询问之间相互独立（即每次询问后应重置 $a$ 数组）。

输入格式

本题读入量较大，建议采用较快的读入方式。

输入共 $T+1$ 行。

第一行，一个正整数 $T$，表示询问的次数。

接下来 $T$ 行，每行两个正整数 $k$ 和 $x$，表示一组询问。

输出格式

输出一行一个 01 串。

01 串的第 $i$ 位表示第 $i$ 个询问的答案：

• 如果对于第 $i$ 个询问，答案是“能”，则 01 串的第 $i$ 位为 1。

• 如果对于第 $i$ 个询问，答案是“不能”，则 01 串的第 $i$ 位为 0。

4
6 36
6 35
5 30
5 31

0101

提示

对于 $100\%$ 的数据，$1\le T\le5\times10^6$，$1\le k \le 60$，$0\le x \le 4 \times 10^{18}$。

测试点编号	$T$	$k$	特殊性质	分数
$1$	$\le100$	$\le10$	无	20
$2$	$\le60$	$\le60$	A
$3$	$\le1\times10^5$		无	30
$4$	$\le5\times10^6$

特殊性质 A：保证 $x=2^{k}-1$。

请注意您实现的常数复杂度。

时空限制均在标程（加快读优化）的 2.5 倍以上。

本题输入输出量较大，我们强烈建议您使用快速读入模板：

char *p1,*p2,buf[1<<20];
inline char gc(){if(p1==p2)p2=(p1=buf)+fread(buf,1,1<<20,stdin);return p1==p2?' ':*p1++;}
inline long long read(){
	register long long s=0; register char c=gc();
	while(c<'0'||c>'9') c=gc();
	while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^48),c=gc();
	return s;
}

x = read() //读入x