311047: CF1926E. Vlad and an Odd Ordering
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
E. Vlad and an Odd Orderingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
Vladislav has $n$ cards numbered $1, 2, \dots, n$. He wants to lay them down in a row as follows:
- First, he lays down all the odd-numbered cards from smallest to largest.
- Next, he lays down all cards that are twice an odd number from smallest to largest (i.e. $2$ multiplied by an odd number).
- Next, he lays down all cards that are $3$ times an odd number from smallest to largest (i.e. $3$ multiplied by an odd number).
- Next, he lays down all cards that are $4$ times an odd number from smallest to largest (i.e. $4$ multiplied by an odd number).
- And so on, until all cards are laid down.
The first line contains an integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases.
The only line of each test case contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 10^9$) — the number of cards Vlad has, and the position of the card you need to output.
OutputFor each test case, output a single integer — the $k$-th card Vladislav lays down.
ExampleInput11 7 1 7 2 7 3 7 4 7 5 7 6 7 7 1 1 34 14 84 19 1000000000 1000000000Output
1 3 5 7 2 6 4 1 27 37 536870912Note
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.
Output
题目大意：
弗拉德有n张编号为1, 2, ..., n的卡片。他想按以下规则将它们排成一行：
1. 首先，按从小到大的顺序放下所有奇数编号的卡片。
2. 接着，放下所有是奇数两倍的卡片（即2乘以一个奇数），也是按从小到大的顺序。
3. 然后，放下所有是奇数三倍的卡片（即3乘以一个奇数），同样按从小到大的顺序。
4. 接下来，放下所有是奇数四倍的卡片（即4乘以一个奇数），继续按从小到大的顺序。
5. 以此类推，直到放下所有的卡片。
问在这个过程中，他放下的第k张卡片是什么？弗拉德一旦放下了一张卡片，就不能再次使用。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 5 × 10^4）——测试用例的数量。
- 每个测试用例包含一行，有两个整数n和k（1 ≤ k ≤ n ≤ 10^9）——弗拉德有的卡片数量和需要输出的卡片的位置。
输出：
- 对于每个测试用例，输出一个整数——弗拉德放下的第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
```
注意：
在前七个测试用例中，n=7。弗拉德按照以下顺序放下卡片：
1. 首先，所有奇数编号的卡片按顺序1, 3, 5, 7。
2. 接着，所有是奇数两倍的卡片按顺序2, 6。
3. 接下来，没有剩余的是奇数三倍的卡片。（弗拉德每种卡片只有一个。）
4. 接着，所有是奇数四倍的卡片，只有一张这样的卡片：4。
5. 没有更多卡片剩下，所以弗拉德停止。
因此，卡片的顺序是1, 3, 5, 7, 2, 6, 4。题目大意： 弗拉德有n张编号为1, 2, ..., n的卡片。他想按以下规则将它们排成一行： 1. 首先，按从小到大的顺序放下所有奇数编号的卡片。 2. 接着，放下所有是奇数两倍的卡片（即2乘以一个奇数），也是按从小到大的顺序。 3. 然后，放下所有是奇数三倍的卡片（即3乘以一个奇数），同样按从小到大的顺序。 4. 接下来，放下所有是奇数四倍的卡片（即4乘以一个奇数），继续按从小到大的顺序。 5. 以此类推，直到放下所有的卡片。 问在这个过程中，他放下的第k张卡片是什么？弗拉德一旦放下了一张卡片，就不能再次使用。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 5 × 10^4）——测试用例的数量。 - 每个测试用例包含一行，有两个整数n和k（1 ≤ k ≤ n ≤ 10^9）——弗拉德有的卡片数量和需要输出的卡片的位置。 输出： - 对于每个测试用例，输出一个整数——弗拉德放下的第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 ``` 注意： 在前七个测试用例中，n=7。弗拉德按照以下顺序放下卡片： 1. 首先，所有奇数编号的卡片按顺序1, 3, 5, 7。 2. 接着，所有是奇数两倍的卡片按顺序2, 6。 3. 接下来，没有剩余的是奇数三倍的卡片。（弗拉德每种卡片只有一个。） 4. 接着，所有是奇数四倍的卡片，只有一张这样的卡片：4。 5. 没有更多卡片剩下，所以弗拉德停止。 因此，卡片的顺序是1, 3, 5, 7, 2, 6, 4。
弗拉德有n张编号为1, 2, ..., n的卡片。他想按以下规则将它们排成一行：
1. 首先，按从小到大的顺序放下所有奇数编号的卡片。
2. 接着，放下所有是奇数两倍的卡片（即2乘以一个奇数），也是按从小到大的顺序。
3. 然后，放下所有是奇数三倍的卡片（即3乘以一个奇数），同样按从小到大的顺序。
4. 接下来，放下所有是奇数四倍的卡片（即4乘以一个奇数），继续按从小到大的顺序。
5. 以此类推，直到放下所有的卡片。
问在这个过程中，他放下的第k张卡片是什么？弗拉德一旦放下了一张卡片，就不能再次使用。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 5 × 10^4）——测试用例的数量。
- 每个测试用例包含一行，有两个整数n和k（1 ≤ k ≤ n ≤ 10^9）——弗拉德有的卡片数量和需要输出的卡片的位置。
输出：
- 对于每个测试用例，输出一个整数——弗拉德放下的第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
```
注意：
在前七个测试用例中，n=7。弗拉德按照以下顺序放下卡片：
1. 首先，所有奇数编号的卡片按顺序1, 3, 5, 7。
2. 接着，所有是奇数两倍的卡片按顺序2, 6。
3. 接下来，没有剩余的是奇数三倍的卡片。（弗拉德每种卡片只有一个。）
4. 接着，所有是奇数四倍的卡片，只有一张这样的卡片：4。
5. 没有更多卡片剩下，所以弗拉德停止。
因此，卡片的顺序是1, 3, 5, 7, 2, 6, 4。题目大意： 弗拉德有n张编号为1, 2, ..., n的卡片。他想按以下规则将它们排成一行： 1. 首先，按从小到大的顺序放下所有奇数编号的卡片。 2. 接着，放下所有是奇数两倍的卡片（即2乘以一个奇数），也是按从小到大的顺序。 3. 然后，放下所有是奇数三倍的卡片（即3乘以一个奇数），同样按从小到大的顺序。 4. 接下来，放下所有是奇数四倍的卡片（即4乘以一个奇数），继续按从小到大的顺序。 5. 以此类推，直到放下所有的卡片。 问在这个过程中，他放下的第k张卡片是什么？弗拉德一旦放下了一张卡片，就不能再次使用。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 5 × 10^4）——测试用例的数量。 - 每个测试用例包含一行，有两个整数n和k（1 ≤ k ≤ n ≤ 10^9）——弗拉德有的卡片数量和需要输出的卡片的位置。 输出： - 对于每个测试用例，输出一个整数——弗拉德放下的第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 ``` 注意： 在前七个测试用例中，n=7。弗拉德按照以下顺序放下卡片： 1. 首先，所有奇数编号的卡片按顺序1, 3, 5, 7。 2. 接着，所有是奇数两倍的卡片按顺序2, 6。 3. 接下来，没有剩余的是奇数三倍的卡片。（弗拉德每种卡片只有一个。） 4. 接着，所有是奇数四倍的卡片，只有一张这样的卡片：4。 5. 没有更多卡片剩下，所以弗拉德停止。 因此，卡片的顺序是1, 3, 5, 7, 2, 6, 4。