В Берляндии довольно холодно (да, даже в мае). Поэтому Монокарпу придется разжечь камин.
У Монокарпа есть большое полено, которое весит \(2^n\) граммов. Монокарп посмотрел прогноз погоды и решил, что ему нужно сжечь \(k\) граммов древесины в камине сегодня, а оставшиеся \(2^n-k\) граммов древесины будут использованы завтра.
За одну минуту Монокарп может использовать свою пилу, чтобы распилить одно из своих поленьев пополам. Изначально у него есть только одно полено, но, конечно, после распиливания полена он получает два новых полена. Если вес полена равен \(x\), то каждое из полученных поленьев имеет вес, равный \(\frac{x}{2}\). Монокарп не может распиливать поленья весом в \(1\) грамм.
Монокарп должен распилить свое полено таким образом, чтобы некоторые из полученных поленьев в сумме весили ровно \(k\) граммов (и поскольку общий вес древесины не изменяется, оставшиеся поленья будут иметь общий вес ровно \(2^n-k\)). Помогите ему рассчитать минимальное количество минут, которое ему придется потратить на распиливание поленьев.
Примечание
В первом наборе входных данных Монокарпу нужно распилить свое полено ровно один раз. Затем у него будет два полена весом по \(2\) грамма.
Во втором наборе входных данных Монокарпу нужно распилить свое полено весом \(4\) грамма один раз, затем распилить одно из полученных поленьев. У него будет одно полено весом \(2\) и два полена весом \(1\), так что он сможет использовать два полена, чтобы получить ровно \(3\) грамма.