Aaronson

给出一个不定方程$x_{0}+2x_{1}+4x_{2}+...+2^{m}x_{m}=n$, 找出一组解$(x_0,x_1,x_2,...,x_m)$, 使得$\displaystyle\sum_{i=0}^{m} x_i$最小, 并且每个$x_i$ ($0 \le i \le m$)都是非负的.

输入包含多组数据, 第一行包含一个整数$T$ $(1 \le T \le 10^5)$表示测试数据组数. 对于每组数据:

第一行包含两个整数$n$和$m$ $(0 \le n,m \le 10^9)$.

对于每组数据, 输出$\displaystyle\sum_{i=0}^{m} x_i$的最小值.

10
1 2
3 2
5 2
10 2
10 3
10 4
13 5
20 4
11 11
12 3

1
2
2
3
2
2
3
2
3
2