说明

我们又来回顾一下汉诺塔问题！这一次，我们还是要把 <math xmlns="http://www.w3.org/1998/Math/MathML">n 个从小到大堆叠的盘子从 <math xmlns="http://www.w3.org/1998/Math/MathML">1 号柱子移动到 <math xmlns="http://www.w3.org/1998/Math/MathML">3 号柱子，并且要按照盘子总的移动次数最少的方案来。

只不过这次要你求解的问题有所不同：你需要计算在整个移动过程中，从上到下的第 <math xmlns="http://www.w3.org/1998/Math/MathML">k 个盘子被移动了几次。

输入格式

包含多组数据，首先输入 <math xmlns="http://www.w3.org/1998/Math/MathML">T，表示有 <math xmlns="http://www.w3.org/1998/Math/MathML">T 组数据。

每个数据一行，是盘子的数目 <math xmlns="http://www.w3.org/1998/Math/MathML">N(1≤n≤60) 和盘号 <math xmlns="http://www.w3.org/1998/Math/MathML">k(1≤k≤n)。

输出格式

样例

2
60 1
3 1

576460752303423488
4