#include<cstdio>

#include<cstring>

#include<algorithm>

#define read(x) x=getint()

using namespace std;

typedef long long LL;

const int p = 1E8 + 9;

const int N = 1E7 + 3;

int getint() {

	int k = 0, fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = k * 10 + c - '0';

	return k * fh;

}

bool np[N];

int prime[N];

LL g[N], sum[N];

void shai() {

	g[1] = 1; sum[1] = 1; int num = 0;

	for(int i = 2; i <= 1E7; ++i) {

		if (!np[i]) {

			prime[++num] = i;

			g[i] = ((LL)i - (LL)i * i) % p;

		}

		for(int j = 1; j <= num; ++j) {

			LL t = prime[j] * i;

			if (t > 1E7) break;

			np[t] = 1;

			if (i % prime[j] == 0) {g[t] = (prime[j] * g[i]) % p; break;}

			g[t] = (g[prime[j]] * g[i]) % p;

		}

		sum[i] = (sum[i - 1] + g[i]) % p;

	}

}

LL S(LL x, LL y) {return (x * (x + 1) / 2 % p) * (y * (y + 1) / 2 % p) % p;}

int main() {

	int T, n, m;

	shai();

	read(T);

	while (T--) {

		read(n); read(m);

		if (n > m) swap(n, m);

		LL ret = 0;

		for(int i = 1, la = 1; i <= n; i = la + 1) {

			la = min(n / (n / i), m / (m / i));

			ret = (ret + (sum[la] - sum[i - 1]) * S(n / i, m / i) % p) % p;

		}

		printf("%lld\n", (ret + p) % p);

	}

	return 0;

}