莫名其妙地又卡在long long上了，我果然又在同一个地方犯逗。
在“在路上，同梦行”群里闹了个大笑话QAQ
#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;
}
QuQ