ll f(ll a,ll m){
	ll s=a*(a+1)/2;
	ll t=(a/m)*(a/m-1)/2;
	return s-t*m*m-a%m*(a/m*m);
}

{
	int @t;
	rep(t){
		int @d,@a,@b;
		if(a==0){
			wt(f(b,d-1));
		}else{
			wt(f(b,d-1)-f(a-1,d-1));
		}
	}
}