RABBIT1  Counting Rabbits
Rabbits are incredible animals. One of their more interesting characteristics is related with their reproduction. If we keep a couple of adult rabbits in optimal conditions of life, it is scientifically proved that, each month, that couple is capable of procreating a new couple of young rabbits. You should know that only the adult couples may procreate and that the time taken by a young couple of rabbits to grow (that is, to become adult) is of 1 month. For the convenience of this task, we will be dealing with immortal rabbits.
Farmer Luis (FL) is a great admirer of rabbits. FL bought in the market 1 couple of adult rabbits (alive, of course) and know wants to raise as many rabbits as he can. Unfortunately, there is a little problem, FL has boxes where he can only put exactly 2^M (1 <= M <= 20) couples of rabbits (neither more nor less). FL can use as many boxes as he wishes as long as he fulfils the condition above. FL would like to know how many couples of rabbits he will not be able to put inside boxes if he raises rabbits for N (1 <= N <= 2147483647) months and then tries to ‘box’ them (put them inside boxes). You should help FL with these calculations. You must consider that FL starts with 1 adult couple of rabbits the 1st month, and that couples of rabbits reproduce and grow as stated in the 1st paragraph.
Input
Line 1: C (1 <= C <= 100), the number of calculations your program will be requested to do
Lines 2C+1: two integers N and M (in that order)
Output
Lines 1C: on each lines print S, which is the number of un'boxed' couples of rabbits.
Example
Input: 1 5 2 Output: 0
Output explanation
After growing couples of rabbits during 5 months, FL has 5 adult couples and 3 young couples (8 couples in total). FL has boxes where can put 2^2 = 4 couples of rabbits, so he can use 2 boxes to ‘box’ all the 8 couples. If FL had instead grown couples of rabbits for 4 months, he would have 5 couples in total; thus 1 couple would have remained un‘boxed’ (the answer would have been 1).
hide comments
smso:
20230610 17:24:48
summary of problem statement:


anihm136:
20190928 22:57:53
How do you get high order fibonacci terms?


amulyagaur:
20171214 12:16:24
Awesome problem! 

akshayvenkat:
20160721 16:13:45
log(n) per test case will TLE? whut? 

minhthai:
20160206 07:24:48
m <= 2^20 is the key for me. nice! 

Lai Manh Tuan:
20151023 23:32:45
Please modify the problem statement. 

Dushyant Singh:
20150704 15:02:07
Most people have done it in 0.00 time! How? I have done it in 0.15! :( 

Hussain Kara Fallah:
20150416 18:53:01
bad statement 

Tushar Ghosh:
20100207 21:35:15
The Author has asked "the number of couples not in the box" in the problem passage, whereas mistakenly mentioned "the number of rabbits not in the box" in the Output. This has caused ambiguity plus three submissions of mine. Hope he looks into it and rectifies the problem 
Added by:  Abel Nieto Rodriguez 
Date:  20080214 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Mindbend 2002 Programming Contest 