#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int n;cin>>n;
	while(n--){
		int c,b;
		cin>>c>>b;
		int cnt=0;
		if((c/b)<=1) {
			cout<<c<<endl;
			continue;
			
		}
		int res=c/b;
		while(res){
			if(res&1) cnt++;
			res=res>>1;
		}
		cout<<cnt*b<<endl
		;
	}
	return 0;
}