C1076 - 下落的小球
题目描述
K个小球会逐个从完全二叉树结构FBT的根部掉落。每当有小球掉落时，它首先会访问一个非终端节点。然后，它会继续向下移动，要么沿着左子树的路径，要么沿着右子树的路径，直到停在FBT的一个叶节点上。
为了确定小球的移动方向，在每个非终端节点上设置了一个标志，其取值为false或true。最初，所有的标志都是false。当访问一个非终端节点时，如果该节点上标志的当前值为false，则小球首先会改变该标志的值，即从false变为true，然后继续沿着该节点的左子树向下移动。
否则，小球也会改变该标志的值，即从true变为false，但会沿着该节点的右子树向下移动。此外，FBT的所有节点都按顺序编号，从深度为1的节点开始，然后是深度为2的节点，依此类推。任何深度的节点都是从左到右编号的。
例如，下图代表了一个最大深度为4的完全二叉树，节点编号为1、2、3、...、15。由于所有的标志最初都设置为false，第一个被投下的小球会在最终停在位置8之前，分别在节点1、节点2和节点4处改变标志的值。
第二个被投下的小球将在节点1、节点3和节点6处改变标志的值，并停在位置12。显然，第三个被投下的小球会在最终停在位置10之前，分别在节点1、节点2和节点5处改变标志的值。
现在考虑一些测试案例，每个测试案例会给出两个值。第一个值是 D，代表FBT的最大深度；第二个值是 I，代表第 I 个被投下的小球。您可以假设 I 的值不会超过给定 FBT 的叶节点的总数。
请编写一个程序来确定每个测试案例的停止位置 P。
输入格式、
第1行，一个正整数T，代表接下来会有T组测试数据
每组测试数据的占一行，包含2个整数D、I，相邻两个整数之间用单个空格隔开，D代表的是完全二叉树的深度，I代表小球的个数
输出格式
对于每组测试数据输出一行结果，该行中输出的是一个整数：即第I个小球最终停止的叶子节点P
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| 5 4 2 3 4 10 1 2 2 8 128 |
12 7 512 3 255 |
数据范围与提示
对于100%的数据满足：$2 \le T \le 1024$，$2 \le D \le 20$，$1 \le I \le 524288$
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式