Problem 1093 --汉诺塔

1093: 汉诺塔

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 106  Solved: 14
[Submit][Status][Web Board][Creator:]

Description

汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚 石柱子,在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始 按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移 动一个圆盘。当所有的圆盘都从梵天穿好的那根柱子上移到另外一根柱子上时,世界就将在一声霹雳中 消灭,而梵塔、庙宇和众生也都将同归于尽。 


        现在,假设全部的 n 个圆盘按正确顺序摆放在最左边的柱子上,从小到大标号 1, 2,  . . . , n。按照游戏规则, 在把全部圆盘移动到最右侧柱子上且移动次数最少的方案中,第 m 次移动的是几号圆盘?


Input

第一行一个 T(1 ≤ T ≤ 105 ), 表示有 T 次询问。 

后面 T 行,每行两个整数 n(1 ≤ n ≤ 50),m(保证 m 不超过最少移动次数),n, m 的含义见题目描述。

Output

对于每次询问,输出一行一个整数,表示圆盘序号。 

Sample Input

2
1 1
2 2

Sample Output

1
2

HINT


当 n = 1 时,只需要 1 步就可以把圆盘从最左端柱子移动到最右端,第 1 次移动的圆盘序号为 1。 



当 n = 2 时,至少需要三步才可以将圆盘按正确顺序移至最右:1-> 中间,2-> 最右,1-> 最右。第 2 次移
动的圆盘序号为 2。 

Source

[Submit][Status]