#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
using namespace std;
const ll p=2009;
ll s1(ll n)
{
	return n*(n+1)/2;
}
ll s2(ll n)
{
	return n*(n+1)*(2*n+1)/6;
}
ll ask(ll up,ll a,ll b)
{
	ll ans=0;
	ans+=s1(min(a,up))+max(0ll,(up-a))*a;//2e8
	ans+=s2(min(min(a,b)-1,up));//2e12
	if(min(min(a,b)-1,up)<min(max(a,b),up))
		ans+=(min(min(a,b)-1,up)+1+min(max(a,b),up))*(min(max(a,b),up)-min(min(a,b)-1,up))/2*min(a,b);//2e12
	ans+=max(0ll,(up-max(a,b)))*a*b;//1e12
	return ans;
}
int main()
{
// #define Isaac
#ifdef Isaac
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
#endif
	int t,x,y,i,j;
	ll ans;
	cin>>t;
	for(;t>=1;t--)
	{
		cin>>x>>y;  ans=0;
		// a=min(i,y-j),b=min(x-i,j),c=min(i,j),d=min(x-i,y-j)
		for(i=0;i<=x;i++)
		{
			ans+=ask(y,i,x-i);// bc+c
			ans+=ask(y,x-i,i);// ad+d
		}
		for(i=0;i<=y;i++)
		{
			ans+=ask(x,y-i,i);// ac+a
			ans+=ask(x,i,y-i);// bd+b
		}
		cout<<ans%p<<endl;
	}	
	return 0;
}