CodeChef submission 27211 (C++ 4.0.0-8) plaintext list. Status: WA, problem C3, contest MAY09. By i0exception (Aniruddha), 2009-05-09 18:26:30.
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cassert>
#define CLRM(x) memset(x,-1,sizeof(x))
#define CLR(x) memset(x,0,sizeof(x))
#define ALL(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
#define VI vector<int> 
#define VVI vector<vector<int> >
#define PII pair<int,int>
#define SZ(x) (int)x.size()
#define LL long long
#define MIN(a,b) (a)<(b)?(a):(b)
#define MAX(a,b) (a)>(b)?(a):(b)
using namespace std;
#define MOD 531169
#define ll long long
 
inline ll mod(ll a, int m)
{
	a %= m;
    if (a < 0) a += m;
    return a;
}
inline ll fastpow (ll a, int b)
{
    ll p = 1;
 
    while (b > 0)
    {
        if (b & 1) p = p * (ll)a % MOD;
        a = (ll)a * a % MOD;
        b >>= 1;
    }
 
    return p;
}
static int inverse(int a, int m)
{
	return fastpow(a, m - 2);
}
 
static int itable[MOD];
static int ftable[MOD];
 
static void setup()
{
    itable[0] = 0;
    ftable[0] = 1;
    for (int i = 1; i < MOD; i++)
    {
        //itable[i] = inverse(i, MOD);
        ftable[i] = mod((ll)ftable[i - 1] * i, MOD);
    }
}
 
static void factorial(int n, int &p, int &m)
{
    if (n < MOD)
    {
        p = 0;
        m = ftable[n];
    }
    else
    {
        int s = n / MOD;
        factorial(s, p, m);
        p += s;
        m = mod(m * (ll)ftable[n % MOD], MOD);
        if (s & 1) m = mod(-m, MOD);
    }
}
 
static int get(int n, int a, int b)
{
    int pa, pb, pc;
    int ma, mb, mc;
    factorial(n, pa, ma);
    factorial(a, pb, mb);
    factorial(b, pc, mc);
    if(pa > pb + pc)
    	return 0;
    mb = mod((ll)mb * mc, MOD);
    return mod((ll)ma * inverse(mb, MOD), MOD);
}
int pr[1024];
int prsz;
int solve(int a, int b)
{
	int i, j, k;
	int t1 = a, t2 = b;
	CLR(pr);
	prsz = 0;
	int lim = min(a, b);
	for(i = 2; i * i <= lim; i = i + 1)
	{
		if(t1 == 1 || t2 == 1)
		{
			break;
		}
		if(t1 % i != 0 || t2 % i != 0)
		{
			continue;
		}
		pr[prsz++] = i;
		while(t1 % i == 0)
		{
			t1 /= i;
		}
		while(t2 % i == 0)
		{
			t2 /= i;
		}
	}
	if(t1 == t2 && t1 != 1)
	{
		pr[prsz++] = t1;
	}
	lim = 1<<prsz;
	int ret = get(a + b, a, b);
	for(i = 1; i < lim; i++)
	{
		int sgn = 1;
		ll prod = 1;
		if(__builtin_popcount(i) % 2 == 1)
		{
			sgn = -1;
		}
		int t = i;
		int cnt = 0;
		while(t)
		{
			if(t & 1)
			{
				prod *= pr[cnt];
			}
			cnt++;
			t>>=1;
		}
		int ta, tb;
		ta = a / prod;
		tb = b / prod;
		int x = get(ta + tb, ta, tb);
		ret = mod(ret + sgn * x, MOD);
	}
	return ret;
}
 
int main()
{
	setup();
	int tes;
	scanf("%d", &tes);
	while(tes--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		int ans = solve(a, b);
		printf("%d\n", ans);	
	}
	return 0;
}