RT

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[105][105][2];
int n,m;
int ans;
int dfs(int st,int now,int cnt,bool fl){//初始有多少，现在有多少，Steve手里有多少，轮到的人
	if(st==0)return 0;
	if(now==0){
		if(fl==0)return dfs(st-cnt,st-cnt,0,0)+cnt;
		else return dfs(cnt,cnt,0,1);
	}
	if(f[now][cnt][fl])return f[now][cnt][fl];
	int tmp=0;
	for(int i=1;i<=min(m,now);i++){
		if(fl)tmp=max(tmp,dfs(st,now-i,cnt+i,0));
		else tmp=max(tmp,dfs(st,now-i,cnt,1));
	}
	return f[now][cnt][fl]=tmp;
}
signed main(){
	int t;
	cin>>t;
	ans=0;
	while(t--){
		memset(f,0,sizeof(f));
		cin>>n>>m;
		cout<<dfs(n,n,0,1)<<endl;
	} 
	return 0;
}