#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
#define int long long
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mxn=1e6;
int dp[mxn];
int ans[mxn];
vector<pair<int,int>> qwq[mxn];
signed main()
{
	int T=read(),i,j;
	for(j=1;j<=T;j++)
	{
		int s=read(),c=read(),i,sum=0;
		if(c<=1000)
		{
			qwq[c].push_back({s,j});
			continue;
		}
		if(s>=2000)
		{
			for(;;)
			{
				if(s<2000) break;
				sum+=c*s,s-=c+1;
			}
		} 
		
//		printf("%lld\n",sum);
		for(i=1;i<=s;i++)
		{
			dp[i]=max(dp[i-1]+i,dp[max(0ll,i-c-1)]+c*i);
//			if(dp[i]==dp[i-1]+i) break;
		}
		ans[j]=sum+dp[max(0ll,s)];
//		cout<<i<<endl;
//		for(int i=1;i<=s;i++)
//			cout<<i<<':'<<dp[i]-dp[i-1]<<endl;
//		cout<<dp[s]<<endl;
//		printf("%lld\n",)
	}
	for(int c=1;c<=1000;c++)
		if(qwq[c].size())
		{
			for(i=1;i<=172800;i++)
			{
				dp[i]=max(dp[i-1]+i,dp[max(0ll,i-c-1)]+c*i);
	//			if(dp[i]==dp[i-1]+i) break;
			}
			for(auto x:qwq[c])
				ans[x.second]=dp[x.first];
		}
	for(i=1;i<=T;i++)
		printf("%lld\n",ans[i]);
}