小球下落

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file fballs.in Output file fballs.out

【题目描述】


    一定数量(k个)的球从一个满二叉树的根上一个接一个掉下来, 每次球先访问非终端节点。然后他继续下落, 或走左子树,或走右子树,直到它停在一个叫FBT的叶子节点。为了标志小球下落的路线, 在每一个非终端节点设一个标志,真或者假。最初, 所有标志都是假, 当一个小球访问一个非终端节点时,如果这个节点标志为假,则标志为真,然后沿左子树走。否则, 同样要改变这个节点的标志,从真变到假,然后沿右子树走。 此外,所有FBT节点都被连续的标号,深度为1的节点从1号开始标,然后标深度为2的,以此类推。 每一层都从左到右开始编号。

     如下图表示一个深度为4编号从1…..15的满二叉树。从所有节点标号为假开始,第一个球将改变1,2,4的标志,最后落在8上。第二个球将改变1,3,6的标志,最后落在12上。很明显,第三个球将改变1,2,5的标志,最后落在10上。

                    


                                         1个深度为4并连续编号的FBT

    现在每组数据给你两个数,第一个数是D,即FBT最大深度,第二个数是I,即第几个球将掉下来。你将要算出第I个球将落在哪个节点上。

    请编写一个程序去实现以上要求。

数据范围:     2<=D<=20, and 1<=I<=524288



【输入格式】


包含L+2行:

第1行:N,表示共有N组数据。(n<=1000)

第2行到第L+1行,每行2个正整数,即

D1 I1

……….

Dk Ik

……….

Dl Il

第L+2行:-1(表示输入文件结束)


【输出格式】

包含L行,每行一个数据,即第I个小球将落在第几个节点上。

【样例输入】

5
4 2
3 4
10 1
2 2
8 128
-1

【样例输出】

12
7
512
3
255
 

【提示】

在此键入。

【来源】

uva679