题目描述

给你两个正整数n和k，二进制字符串Sn的形成规则如下：

S1 = "0"

当i > 1时，Si = Si-1 + "1" + reverse(invert(Si-1))

其中+表示串联操作，reverse(x)返回反转x后得到的字符串，而invert(x)则会翻转x中的每一位（0变为1，而1变为0）。

例如，符合上述描述的序列的前4个字符串依次是：

S1 = "0"

S2 = "011"

S3 = "0111001"

S4 = "011100110110001"

请你返回Sn的第k位字符，题目数据保证k一定在Sn长度范围以内。

输入格式

n = 3, k = 1

第一行有一个正整数T（1<=T<=5），表示有T组测试数据。

接下来有T行，每行有2个正整数：N K。N范围[2, 30]；

输出格式

"0"

解释：S3为"0111001"，其第1位为"0"。

输出有T行，每行一个1或0

2
4 11
5 14

1
0

</p>

提示

本题共 10 个测试点。

来源

递归