题目描述

Vlad有 $n$ 张牌，编号为 $1,2,...,n$。他想把这些牌按如下方法排成一排：

• 首先，他把所有奇数牌从小到大依次铺开。

• 接着，他从小到大铺开所有奇数的 $2$ 倍（即 $2$ 乘以奇数）的牌。

• 接着，他从小到大铺开所有是奇数的 $3$ 倍（即 $3$ 乘以奇数）的牌。

• 接着，他从小到大铺开所有是奇数的 $4$ 倍（即 $4$ 乘以奇数）的牌。

• 依此类推，直到所有的牌都放完。

在这个过程中，他放下的第 $k$ 张牌是什么？

一旦Vlad放下一张牌，他就不能再用这张牌了。

输入格式

第一行包含一个整数 $t$ $(1≤t≤5⋅10^4)$ 表示测试用例数。

每个测试用例包括一行：两个整数 $n$ 和 $k$ $(1≤k≤n≤10^9)$ ，分别表示 Vlad 拥有的卡片数量，以及需要输出的卡片的位置。

输出格式

对于每个测试用例，输出一行一个整数，表示Vlad铺开的第 $k$ 张牌。

样例

11
7 1
7 2
7 3
7 4
7 5
7 6
7 7
1 1
34 14
84 19
1000000000 1000000000

1
3
5
7
2
6
4
1
27
37
536870912

样例说明

In the first seven test cases, $n=7$ . Vladislav lays down the cards as follows:

• First — all the odd-numbered cards in the order $1$ , $3$ , $5$ , $7$ .
• Next — all cards that are twice an odd number in the order $2$ , $6$ .
• Next, there are no remaining cards that are $3$ times an odd number. (Vladislav has only one of each card.)
• Next — all cards that are $4$ times an odd number, and there is only one such card: $4$ .
• There are no more cards left, so Vladislav stops.

Thus the order of cards is $1$ , $3$ , $5$ , $7$ , $2$ , $6$ , $4$ .

来源

Codeforces 1926E，英文题名 Vlad and an Odd Ordering。