У Владислава есть \(n\) карт с номерами \(1, 2, \dots, n\). Он хочет выложить их в ряд следующим образом:
- Сначала он выкладывает все карты с нечетными номерами от наименьшего к наибольшему.
- Затем он выкладывает все карты, которые являются удвоенными нечетными числами, от наименьшего к наибольшему (т.е., \(2\) умноженное на нечётное число).
- Затем он выкладывает все карты, которые являются нечетными числами, умноженными на \(3\), от наименьшего к наибольшему (т.е., \(3\) умноженное на нечётное число).
- Затем он выкладывает все карты, которые являются нечетными числами, умноженными на \(4\), от наименьшего к наибольшему (т.е., \(4\) умноженное на нечётное число).
- И так далее, пока все карты не будут выложены.
Какая карта будет
\(k\)-й, которую он выложит в этом процессе? После того, как Влад положил карту, он не может использовать ее снова.
Выходные данные
Для каждого набора входных данных выведите одно целое число — \(k\)-ю карту, которую выложит Влад.
Примечание
В первых семи наборах входных данных примера \(n=7\). Влад выкладывает карты следующим образом:
- Сначала — все карты с нечетными номерами в порядке \(1\), \(3\), \(5\), \(7\).
- Затем — все карты, которые являются удвоенными нечетными числами, в порядке \(2\), \(6\).
- Затем нет оставшихся карт, которые являются нечетными числами, умноженными на \(3\). (У Влада есть только по одной карте каждого числа.)
- Затем — все карты, которые являются нечетными числами, умноженными на \(4\), и есть только одна такая карта: \(4\).
- Больше карт не осталось, поэтому Влад останавливается.
Таким образом, порядок карт будет
\(1\),
\(3\),
\(5\),
\(7\),
\(2\),
\(6\),
\(4\).
Примеры
| № | Входные данные | Выходные данные |
|
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
3
5
7
2
6
4
1
27
37
536870912
|