Recently, Peter saw the equation x0+2x1+4x2+...+2mxm=nx0+2x1+4x2+...+2mxm=n. He wants to find a solution (x0,x1,x2,...,xm)(x0,x1,x2,...,xm) in such a manner that ∑i=0mxi∑i=0mxi is minimum and every xixi (0≤i≤m0≤i≤m) is non-negative.

Input

There are multiple test cases. The first line of input contains an integer TT (1≤T≤105)(1≤T≤105), indicating the number of test cases. For each test case:

The first contains two integers nn and mm (0≤n,m≤109)(0≤n,m≤109).

Output

For each test case, output the minimum value of ∑i=0mxi∑i=0mxi.

Sample Input

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

Sample Output

1
2
2
3
2
2
3
2
3
2

题意:满足上面等式的情况下，x和最小

贪心思想，递归代码

#include"stdio.h"
#include"math.h"
#include"string.h"
#include"algorithm"
#include"iostream"
using namespace std;
typedef long long ll;
ll dfs(ll x,ll y)
{
	if(x<=0)
		return 0;
	while(y>x) y/=2;
	ll k=x/y;
	if(k*y==x)
		return k;
	else
		return k+dfs(x-k*y,y);
}
int main()
{
	ll y,n,m,w;
	cin>>w;
	while(w--)
	{
		cin>>n>>m;
		if(m>=30)//m>30,y值无法正确计算，会出现runtime error
		m=29;
		y=pow(2,m);
		cout<<dfs(n,y)<<endl;
	}
	return 0;
}