gistfile1.txt

#include <bits/stdc++.h>
using namespace std;

typedef long long int llint;

llint minPrimeFactor[100000000];

void sieveGen(llint limit)
{
    minPrimeFactor[1] = 1;
    for (llint i = 2 ; i <= limit ; i++) minPrimeFactor[i] = i;
    for (llint i = 4 ; i <= limit ; i += 2) minPrimeFactor[i] = 2;
    for (llint i = 3 ; i * i <= limit; i++)
    {
        if (minPrimeFactor[i] == i)
        {
            for (llint j = i * i ; j <= limit; j += i) if (minPrimeFactor[j] == j) minPrimeFactor[j] = i;
        }
    }
}

vector <llint> factor(llint x)
{
    vector <llint> vct;
    while (x != 1)
    {
        vct.push_back(minPrimeFactor[x]);
        x = x / minPrimeFactor[x];
    }
    return vct;
}

main()
{
	//freopen("equa.inp","r",stdin);
	//    +
	//freopen("equa.out","w",stdout);
	llint count; cin >> count;
	pair <llint, llint> arr[count - 1];
	for (llint i = 0 ; i <= count - 1 ; i++)
	{
		llint a, b; 
		cin >> a >> b;
		arr[i].first = a; arr[i].second = b;
	};
	llint max = -1e9;
	for (llint i = 0 ; i <= count - 1 ; i++) 
	{
		if (arr[i].second > max) max =arr[i].second;
		if (arr[i].first > max) max = arr[i].first;
		if (arr[i].second > max) max =arr[i].second;
	}
	sieveGen(max);
	for (llint i = 0 ; i <= count - 1 ; i++)
	{
		llint t1 = arr[i].first, t2 = arr[i].second;
		vector <llint> vct = factor(t1);
		/*
		map <llint, llint> out1;
		llint size1 = vct1.size();
		for (llint i = 0 ; i <= size1 - 1 ; i++) if (out1.count(vct1[i])) out1[vct1[i]]++; else out1[vct1[i]] = 1;
		set <llint> s1 (vct1.begin(), vct1.end());
		vct1.assign(s1.begin(), s1.end());
		size1 = vct1.size();
		
		for (llint i = 0 ; i <= size1 - 1 ; i++)  cout << "[" << vct1[i] << "] @ [" << out1[vct1[i]] << "]\n";
		*/
		
		
		vector <llint> vct2 = factor(t2);
		/*
		map <llint, llint> out2;
		llint size2 = vct2.size();
		for (llint i = 0 ; i <= size2 - 1 ; i++) if (out2.count(vct2[i])) out2[vct2[i]]++; else out2[vct2[i]] = 1;
		set <llint> s2 (vct2.begin(), vct2.end());
		vct2.assign(s2.begin(), s2.end());
		size2 = vct2.size();
		
		for (llint i = 0 ; i <= size2 - 1 ; i++)  cout << "[" << vct2[i] << "] @ [" << out2[vct2[i]] << "]\n";
		*/
		
		//vct.insert(vct.end(), vct1.begin(), vct1.end());
		vct.insert(vct.end(), vct2.begin(), vct2.end());
		map <llint, llint> out;
		llint size = vct.size();
		for (llint i = 0 ; i <= size - 1 ; i++) if (out.count(vct[i])) out[vct[i]]++; else out[vct[i]] = 1;
		set <llint> s (vct.begin(), vct.end()); vct.assign(s.begin(), s.end());
		size = vct.size();
		llint o = 1;
		for (llint i = 0 ; i <= size - 1 ; i++)
		{
			//cout << "[" << vct[i] << "] @ [" << out[vct[i]] << "]\n";
			o *= 2 * out[vct[i]] + 1;
		};
		cout << o << endl;
	}
}