Crazygirl is a crazy fan of XBOX games. Today, she’s here middle in a competition, in which the winner will be rewarded with an opportunity of working in the XBOX Company as a game testing player. Now, here comes the final game. As Cazygirl get a draw with the other competitor, Lich King, she must beat Lich this time.
The game is quite simple. There are n balls numbered from 1 to n and k boxes B₁, B₂,…, B_k satisfying following conditions:
1.  With any ball x in box B_i, there must be ball 2x in box B_i+1 if there is a box B_i+1;
2.  With any ball x in box B_i, there must be ball y in box B_i-1 satisfying 2y=x if there is a box B_i-1;
3.  You can’t put a ball in two different boxes at the same time;
4.  Your score is the number of balls in box B₁;
5.  The player who get the highest score win the game of course.
So, you should tell Crazygirl the highest score she can get.

The first line is the number of test cases.
Each test case has one line containing two integers n and k, meaning that there are n balls and k boxes. ( 1≤n≤10¹⁰⁰⁰⁰, 2≤k≤25 )

For each test case, output one line that contains an integer equals to the highest score you can get.

3
10 2
7 5
8 3

4
0
1

2013ACM-ICPC杭州赛区全国邀请赛