RABBIT1 - Counting Rabbits

no tags 

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 2-C+1: two integers N and M (in that order)

Output

Lines 1-C: 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
amulyagaur: 2017-12-14 12:16:24

Awesome problem!

akshayvenkat: 2016-07-21 16:13:45

log(n) per test case will TLE? whut?

minhthai: 2016-02-06 07:24:48

m <= 2^20 is the key for me. nice!

Lai Manh Tuan: 2015-10-23 23:32:45

Please modify the problem statement.

Dushyant Singh: 2015-07-04 15:02:07

Most people have done it in 0.00 time! How? I have done it in 0.15! :-(

Hussain Kara Fallah: 2015-04-16 18:53:01

bad statement

Tushar Ghosh: 2010-02-07 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:2008-02-14
Time limit:0.184s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Mindbend 2002 Programming Contest