1958C.md (1915B)
1 Source: https://codeforces.com/problemset/problem/1958/C 2 3 C. Firewood 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 It's pretty cold in Berland (yes, even in May). So Monocarp has to light his fireplace. 22 23 Monocarp has a big log of wood, which weighs $2^n$ grams. Monocarp has watched the weather forecast and decided that he has to burn $k$ grams of wood in the fireplace today, and the remaining $2^n-k$ grams of wood will be used tomorrow. 24 25 In one minute, Monocarp can use his saw to split one of his logs in half. Initially he has only one log, but of course, after splitting a log, he gets two new logs. If the weight of the log is $x$, then each of the resulting logs has weight equal to $\frac{x}{2}$. Monocarp can't split logs of weight $1$ gram. 26 27 Monocarp has to cut his log in such a way that some of the resulting logs weigh exactly $k$ grams in total (and since the total weight of wood doesn't change, the remaining logs will have a total weight equal to exactly $2^n-k$). Help him to calculate the minimum number of minutes he has to spend cutting the logs. 28 29 Input 30 31 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 Each test case consists of one line containing two integers $n$ and $k$ ($1 \le n \le 60$; $1 \le k \le 2^n-1$). 34 35 Output 36 37 For each test case, print one integer — the minimum number of minutes Monocarp has to spend splitting the wood. 38 39 Example 40 41 Input 42 43 ``` 44 4 45 46 2 2 47 48 2 1 49 50 10 3 51 52 50 36679020707840 53 ``` 54 55 Output 56 57 ``` 58 1 59 2 60 10 61 16 62 ``` 63 64 Note 65 66 In the first test case, Monocarp has to cut his log exactly once. Then he will have two logs weighing $2$ grams each. 67 68 In the second test case, Monocarp has to cut his log of $4$ grams once, then cut one of the resulting logs. He will have one log of weight $2$ and two logs of weight $1$, so he can use two logs to get exactly $3$ grams.