← 返回题目列表

Codeforces · 1926/E

E. 弗拉德和奇怪的订单

中文机器翻译题面 查看原题

Vladislav 有 $$$n$$$ 卡,编号为 $$$1, 2, \dots, n$$$。他想把它们排成一排,如下所示:

- 首先,他从小到大放下所有奇数牌。
- 接下来,他从最小到最大放下所有奇数两倍的牌(即 $$$2$$$ 乘以奇数)。
- 接下来,他从最小到最大放下所有 $$$3$$$ 乘以奇数的牌(即 $$$3$$$ 乘以奇数)。
- 接下来,他从最小到最大放下所有 $$$4$$$ 乘以奇数的牌(即 $$$4$$$ 乘以奇数)。
- 依此类推,直到所有牌都放下。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — 测试用例的数量。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 10^9$$$) — Vlad 拥有的牌数,以及需要输出的牌的位置。

输出

对于每个测试用例,输出一个整数 - Vladislav 放置的第 $$$k$$$ 张牌。

示例

输入 #1

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

输出 #1

1
3
5
7
2
6
4
1
27
37
536870912

注意

在前七个测试用例中,$$$n=7$$$。弗拉迪斯拉夫 (Vladislav) 放下牌如下:

- 首先 — 所有奇数牌的顺序为 $$$1$$$、$$$3$$$、$$$5$$$、$$$7$$$。
- 下一个 — 所有两倍于奇数的牌,顺序为 $$$2$$$、$$$6$$$。
- 接下来,没有剩余的牌是 $$$3$$$ 乘以奇数。 (弗拉迪斯拉夫每张牌只有一张。)
- 下一个 — 所有 $$$4$$$ 乘以奇数的牌,并且只有一张这样的牌:$$$4$$$。
- 没有更多的牌了,所以 Vladislav 停止了。