Description

    你们一定听说过汉诺塔问题吧。这个问题是说有3个柱子和N个不同大小的圆盘，初始时所有的盘子都在第一个柱子上，最大的圆盘在最下面，最小的圆盘在最上面，从大到小放置。每一次你可以从任意柱子上把最上面的盘子拿走放到任意其他盘子上，但是拿走的盘子只能放到半径比它大的盘子的上面。问题就是如何用最少的次数把所有盘子从第一个柱子移到第三个柱子。     事实上，汉诺塔问题并不仅仅只有3个柱子，而是有M个柱子，请你们计算当有M个柱子时把N个盘子从第一个柱子移到最后一个柱子最少要几次操作。

Input

输入有多组数据，第一行是一个整数N，表示有N组数据。接下来N行每一行有两个整数，分别表示盘子数和柱子数，盘子数<=30,3<=柱子数<=63.

Output

输出N行，第i行表示第i组数据需要的最少操作数。

Sample

Input

2
2 3
16 14

Output

3
37

Source: kokopelli