Codeforces Round 928 (Div. 4) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

bitmasks

data structures

dp

implementation

math

number theory

*1500

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Vlad and an Odd Ordering

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVladislav 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.

Input

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.

Output

For each test case, output a single integer — the $$$k$$$-th card Vladislav lays down.

Example

Input

117 17 27 37 47 57 67 71 134 1484 191000000000 1000000000

Output

1 3 5 7 2 6 4 1 27 37 536870912

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/09/2024 10:22:47 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|