1 #include<cmath>
 2 #include<queue>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<cstdlib>
 6 #include<cstring>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define N 10000010
10 #define RG register
11 #define mo 100000009
12 #define inf 0x3f3f3f3f
13 #define Inf 99999999999999999LL
14 using namespace std;
15 typedef long long LL;
16 bool vis[N];
17 int T,m,n,ans,loc,top,f[N],pre[N],sta[N];
18 inline int Abs(RG const int &a){return a>0?a:-a;}
19 inline int Max(RG const int &a,RG const int &b){return a>b?a:b;}
20 inline int Min(RG const int &a,RG const int &b){return a>b?b:a;}
21 inline int gi(){
22     RG int x=0;RG bool flag=0;RG char c=getchar();
23     while((c<‘0‘||c>‘9‘)&&c!=‘-‘) c=getchar();
24     if(c==‘-‘) c=getchar(),flag=1;
25     while(c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘,c=getchar();
26     return flag?-x:x;
27 }
28 inline void init(){
29     f[1]=1;
30     for (RG int i=2;i<N;++i){
31     if(!vis[i]){
32         f[i]=1-i;
33         sta[++top]=i;
34     }
35     for (RG int j=1;j<=top&&i*sta[j]<N;++j){
36         vis[i*sta[j]]=1;
37         if(i%sta[j]==0){
38         f[i*sta[j]]=f[i];
39         break;
40         }
41         f[i*sta[j]]=((LL)f[i]*(LL)f[sta[j]])%mo;
42     }
43     }
44     for (RG int i=1;i<N;++i) pre[i]=(pre[i-1]+f[i])%mo;
45 }
46 inline LL sum(RG LL now){
47     if(now&1) return (now+(LL)((now-1)/2)*now)%mo;
48               return (now+(LL)(now-1)*(now/2))%mo;
49 }
50 inline void work(){
51     n=gi();m=gi();
52     if(m<n) swap(m,n);
53     /*for (RG int i=1;i<=n;++i)
54       ans=( ans+ ( ( ( (LL)i*sum(n/i) )%mo *(LL)sum(m/i) )%mo *f[i])%mo )%mo;*/
55     for (RG int i=1;i<=n;i=loc+1){
56     //cout<<i<<endl;
57     loc=Min(m/(m/i),n/(n/i));
58     //cout<<loc<<endl;
59     RG LL a=(sum(loc)-sum(i-1))%mo;
60     //cout<<"cfdsji"<<endl;
61     RG LL b=sum(m/i);
62     //cout<<"dsji"<<endl;
63     RG LL c=sum(n/i);
64     //cout<<"ji"<<endl;
65     RG LL d=(pre[loc]-pre[i-1])%mo;
66     cout<<a<<‘ ‘<<b<<‘ ‘<<c<<‘ ‘<<d<<endl;
67     cout<<"congratulations!"<<endl;
68     ans=(ans+( ( ((a*b)%mo) *c%mo) *d%mo))%mo;
69     }
70     printf("%d\n",ans);
71 }
72 int main(){
73     freopen("2394.in","r",stdin);
74     freopen("2394.out","w",stdout);
75     init();
76     /*for (RG int i=1;i<=1000;++i) cout<<pre[i]<<‘ ‘;
77       cout<<endl;*/
78     T=gi();
79     while(T--) work();
80     fclose(stdin);
81     fclose(stdout);
82     return 0;
83 }