В Берляндии довольно холодно (да, даже в мае). Поэтому Монокарпу придется разжечь камин.
У Монокарпа есть большое полено, которое весит $$$2^n$$$ граммов. Монокарп посмотрел прогноз погоды и решил, что ему нужно сжечь $$$k$$$ граммов древесины в камине сегодня, а оставшиеся $$$2^n-k$$$ граммов древесины будут использованы завтра.
За одну минуту Монокарп может использовать свою пилу, чтобы распилить одно из своих поленьев пополам. Изначально у него есть только одно полено, но, конечно, после распиливания полена он получает два новых полена. Если вес полена равен $$$x$$$, то каждое из полученных поленьев имеет вес, равный $$$\frac{x}{2}$$$. Монокарп не может распиливать поленья весом в $$$1$$$ грамм.
Монокарп должен распилить свое полено таким образом, чтобы некоторые из полученных поленьев в сумме весили ровно $$$k$$$ граммов (и поскольку общий вес древесины не изменяется, оставшиеся поленья будут иметь общий вес ровно $$$2^n-k$$$). Помогите ему рассчитать минимальное количество минут, которое ему придется потратить на распиливание поленьев.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Каждый набор входных данных состоит из одной строки, содержащей два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 60$$$; $$$1 \le k \le 2^n-1$$$).
Для каждого набора входных данных выведите одно целое число — минимальное количество минут, которое Монокарпу придется потратить на распиливание поленьев.
42 22 110 350 36679020707840
1 2 10 16
В первом наборе входных данных Монокарпу нужно распилить свое полено ровно один раз. Затем у него будет два полена весом по $$$2$$$ грамма.
Во втором наборе входных данных Монокарпу нужно распилить свое полено весом $$$4$$$ грамма один раз, затем распилить одно из полученных поленьев. У него будет одно полено весом $$$2$$$ и два полена весом $$$1$$$, так что он сможет использовать два полена, чтобы получить ровно $$$3$$$ грамма.
| Kotlin Heroes: Episode 10 |
|---|
| Закончено |
