Dropping Balls

內容 ：

有K個球從一完整二元樹（fully binary tree, FBT）的樹根（root）一個一個往下掉。當這個球遇到非終端節點時，可能往左子樹跑，也可能往右子樹跑，如此直到這顆球到達終端節點（也就是樹葉）為止。至於在非終端節點時球該往左或往右的決定乃是由2個值 true, false 來控制的。如果這非終端節點的現在的值為 false，則球來的時候會往左子樹走，但是這個值會變為 true。如果這非終端節點的現在的值為 true，則球來的時候會往右子樹走，但是這個值會變為 false。請注意：一開始時所有非終端節點的值均為 false。另外，在完整二元樹中所有的節點被依序編號，從上（深度 = 1）到下，由左到右。請參考下圖。

舉例來說，上面的圖為深度為4的完整二元樹。第一顆球往下掉會經過節點1、2、4最後落在節點8中。第二顆球往下掉則會經過節點1、3、6最後落在節點12中。第三顆球往下掉會經過節點1、2、5最後落在節點10中。

給你完整二元樹的深度D以及落下的第I個球，請你寫一個程式算出第I個球落在終端節點的編號。

輸入說明 ：

輸入的第一列有一個整數，代表以下有幾組測試資料。
每組測試資料一列有2個整數D,I（2 <= D <= 20, 1 <= I <= 524288）。

輸出說明 ：

對每組測試資料輸出一列，第I個球落在終端節點的編號。

範例輸入 ：

5
4 2
3 4
10 1
2 2
8 128

範例輸出 ：

12
7
512
3
255

測試102-1

在ASCII CODE 中，每個字元需要使用 8 bit來存資料。當檔案只包含0123456789AB 十二種字元時，可二進制重新編碼以節省空間，假設新編碼如下：

表3.2.1

二進制	字元
00	A
01	B
100	0
101	1
1100	2
1101	3
11100	4
11101	5
111100	6
111101	7
111110	8
111111	9

例如編碼10100110001 對應到的字元為 1A2B。在猜數字的遊戲過程中，會選定不重複的數字排列當做答案，再由玩家來猜數字，再算出幾A幾B，其遊戲過程可用表3.2.1的編碼紀錄(答案為何，幾A幾B如何算出，不是這次題目考慮的範圍)。例如玩家猜數字6789，算出(0A0B)，則把這過程6789 (0A0B)以1111001111011111101111111000010001編碼，為了讓選手方便對照剛剛的編碼，我們將6789 (0A0B) 編碼拆解成111100 (6) 111101 (7) 111110 (8) 111111 (9) 100 (0) 00 (A) 100 (0) 01 (B)；

若玩家猜數字1253，算出(2A1B)，這過程1253(2A1B)以表3.2.1的方式編碼紀錄為

101  1100  11101  1101  1100  00  101  01

(輸入檔案會省略空白，空白的存在是為了方便讀題)

輸入說明：

第1行的數字n代表有幾筆資料要測試，而n的值介於1和5之間，之後每行為0和1所組成的編碼字串，字串長度<=34，對應到一次猜數字的遊戲過程。在測試檔案中，每個編碼字串均可正確的對應到編碼表中的編碼。

輸出說明：

從第1行起每行將輸入之編碼字串，轉成玩家猜的數字及其幾A幾B的結果。（輸出英文字均為大寫，選手請注意。數字和其幾A幾B的結果以”,”分開。）

輸入檔案1：【檔名：in1.txt】

4

1111001111011111101111111000010001

101110011101110111000010101

11100110111001011110001

111011100110111100110100

輸入檔案2：【檔名：in2.txt】

2

1011100100111111110000

1011100110111100110001

輸出範例：【檔名：out.txt】

6789,0A0B

1253,2A1B

4321,4B

5234,3A

1209,2A

1234,2B