原題鏈接

PRoblem Chloe, the same as Vladik, is a competitive programmer. She didn’t have any problems to get to the olympiad like Vladik, but she was confused by the task proposed on the olympiad. Let’s consider the following algorithm of generating a sequence of integers. Initially we have a sequence consisting of a single element equal to 1. Then we perform (n?-?1) steps. On each step we take the sequence we’ve got on the previous step, append it to the end of itself and insert in the middle the minimum positive integer we haven’t used before. For example, we get the sequence [1,?2,?1] after the first step, the sequence [1,?2,?1,?3,?1,?2,?1] after the second step. The task is to find the value of the element with index k (the elements are numbered from 1) in the obtained sequence, i. e. after (n?-?1) steps. Please help Chloe to solve the problem!

Input The only line contains two integers n and k (1?≤?n?≤?50, 1?≤?k?≤?2n?-?1).

Output Print single integer — the integer at the k-th position in the obtained sequence.

Example Input 3 2 Output 2 Input 4 8 Output 4

Note In the first sample the obtained sequence is [1,?2,?1,?3,?1,?2,?1]. The number on the second position is 2. In the second sample the obtained sequence is [1,?2,?1,?3,?1,?2,?1,?4,?1,?2,?1,?3,?1,?2,?1]. The number on the eighth position is 4.

思路：從每個(gè)數(shù)字出現(xiàn)的位置找規(guī)律 1出現(xiàn)在1，3，5，7，9，11，13，15……位置（從2^0開始，間隔2^1，即1+2n，即(1+2n)*2^0，即質(zhì)因子有0個(gè)2） 2出現(xiàn)在2，6，10，14……位置（從2^1開始，間隔2^2，即2+4n，即(1+2n)*2^1，即質(zhì)因子有1個(gè)2） 3出現(xiàn)在4，12……位置（從2^2開始，間隔2^3，即4+8n，即(1+2n)*2^2，即質(zhì)因子有2個(gè)2） 4出現(xiàn)在8……位置（從2^3開始，間隔2^4，即8+16n，即(1+2n)*2^3，即質(zhì)因子中有3個(gè)2）

AC代碼：

優(yōu)化一下

高技巧性位運(yùn)算： 數(shù)n的位置是奇數(shù)個(gè)2^(n-1)，該位置的二進(jìn)制第n-1位一定是1，大于n-1的位可能為1，小于n-1的位一定為0；而2^(n-1)的二進(jìn)制只有第n-1位是1，通過位對比就能得出答案。