#include<bits/stdc++.h>
#define int long long
using namespace std;
int s,c,ans,T;
int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x*f;
}
int f(int x,int y){
	int mid=y+(x-1)*c; if (mid>s) return -y;
	return ((s+mid+1)*(s-mid)+(c-1)*(y+mid)*x)>>1;
}
signed main(){
	T=read();while (T--){
		s=read();c=read()+1;ans=0;  
		/*for (int i=0;i<=(s-1)/c+1;i++)
			for (int j=1;j<=s;j++)
				ans=max(ans,f(i,j)); */
		const int limit=(s-1)/(c-1)+1;
		for (int i=max(limit-100,0ll);i<=limit;i++){
			int l=0,r=s,res=s;while (l+2<r){
				int mid1=l+(r-l)/3,mid2=l+(r-l)/3*2;
				int ans1=f(i,mid1),ans2=f(i,mid2);
				if (ans1>=ans2) res=mid1,r=mid2;
				else res=mid2,l=mid1;
			}
			for (int j=max(0ll,res-20);j<=min(s,res+20);j++) ans=max(ans,f(i,j));
			for (int j=max(0ll,s-20);j<=s;j++) ans=max(ans,f(i,j));
		}
		for (int i=0;i<=min(100ll,limit);i++){
			int l=0,r=s,res=s;while (l+2<r){
				int mid1=l+(r-l)/3,mid2=l+(r-l)/3*2;
				int ans1=f(i,mid1),ans2=f(i,mid2);
				if (ans1>=ans2) res=mid1,r=mid2;
				else res=mid2,l=mid1;
			}
			for (int j=max(0ll,res-20);j<=min(s,res+20);j++) ans=max(ans,f(i,j));
			for (int j=max(0ll,s-20);j<=s;j++) ans=max(ans,f(i,j));
		}
		printf("%lld\n",ans);
	}
	return 0;
}