小Z的麻烦

时间限制：20s 空间限制：128MB

小Z最近遇上了大麻烦，他的数学分析挂科了。于是他只好找数分老师求情。善良的数分老师答应不挂他，但是要求小Z帮助他一起解决一个难题

问题是这样的，现在有n个标号为1～n的球和m个盒子，每个球都可以放进且只能放进一个盒子里面，但是要满足如下的规则：

1. 若把标号为i的球放进了第j个盒子，那么标号为2*i的球一定要在第j+1个盒子里面(若j<m)

2. 若把标号为i的球放进了第j个盒子，并且k*2=i，那么标号为k的球一定要在第j-1个盒子里面(若j>1)

小Z的数分老师想要知道，给定了n和m的时候，第一个盒子最多能放进去多少个球。事实上，他已经推算出了公式，但是需要检验当n趋向于无穷大时是否仍然满足这个公式，因此n可能会非常大。

本题包含多组数据，第一行为一个数(T<=20)，表示数据组数；以下T行，每组数据一行，包括两个数n和m。

每组数据输出一行，包括一个数，即第一个盒子最多能放进多少个球。

 2
10 2
10 3

4
1

样例解释：
(1).{1,3,4,5}, {2,6,8,10}
(2).{1},{2},{4}
对于100%的数据,n<=10^10000,2<=m<=25

没有写明来源