Inverse Binomial Coefficient

All submissions for this problem are available.
The binomial coefficient C(N, K) is defined as N! / K! / (N − K)! for 0 ≤ K ≤ N.
Here N! = 1 * 2 * ... * N for N ≥ 1, and 0! = 1.
You are given integers n and R.
You need to find the smallest K in the range {0, 1, ..., 2^{n} − 1}, for which C(2^{n} − 1, K) mod 2^{n} = R.
Here A mod B denotes the remainder of the division of A by B. If no such K exists output 1.
Input
The first line of the input contains an integer T, denoting the number of test cases.
The description of T test cases follows.
The only line of each test case contains two spaceseparated integers n and R.
Output
For each test case output the answer on the separate line.
Constraints
 1 ≤ T ≤ 100
 1 ≤ n ≤ 120
 0 ≤ R < 2^{n}
Example
Input: 4 1 0 1 1 3 7 4 3 Output: 1 0 1 7
Explanation
Example case 1. We have C(1, 0) = C(1, 1) = 1. Hence C(1, K) mod 2 ≠ 0 for all K. Therefore, the answer is 1.
Example case 2. Since C(1, 0) mod 2 = 1, the answer is 0.
Example case 3. Since C(7, 0) mod 8 = 1 ≠ 7 and C(7, 1) mod 8 = 7 mod 8 = 7, the answer is 1.
Example case 4. Here C(15, 7) mod 16 = 15! / 7! / 8! mod 16 = 6435 mod 16 = 3. It can be shown that for all smaller values of K we have C(15, K) mod 16 ≠ 3. Therefore, the answer is 7.
Author:  anton_lunyov 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/INVBINCF 
Tags  anton_lunyov, april13, factorial, hard, modulo 
Date Added:  11032013 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions