#include <bits/stdc++.h>
using namespace std;
int n;
const int INF = 1e6;
vector<long long> inp;
vector<bool> fakeprime(INF+1, true);
vector<int> prime;
void gen_prime()
{
	fakeprime[0] = fakeprime[1] = false;
	for(int i =2; i<=INF; i++)
	{
		if(fakeprime[i])
		for(long long j = (long long)i*i; j<=INF; j+=(long long)i) fakeprime[j] = false;
	}
	for(int i =2; i<=INF; i++) if(fakeprime[i]) prime.push_back(i);

	
}

int cnt_primeuoc(long long a)
{
	int res = 0;
	for(int  x: prime)
	{
		if( (long long)x*x > a) break;
		if(a % x == 0)
		{
			int cnt = 0;
			while(a % x == 0)
			{
				cnt++;
				a /= x;
			}
			res+=cnt;
		}
		
	}
	if(a > 1) res++;
	return res;
}

long long gcd(long long a, long long b)
{
	if(b == 0 ) return a;
	return gcd(b, a % b);
}

void sub1()
{
	long long ucln = gcd(inp[1], inp[2]);
	long long bcnn = (inp[1] * inp[2]) /  ucln;
//	cout << ucln << " " << bcnn << endl;
	long long tmp1 = cnt_primeuoc(min(inp[1], inp[2])) + cnt_primeuoc(max(inp[1], inp[2]) / ucln);
	// << cnt_primeuoc(min(inp[1], inp[2]));
	long long tmp2 = cnt_primeuoc(bcnn / inp[1]) + cnt_primeuoc(bcnn / inp[2]);
	cout << min(tmp1,tmp2) << " " << 2 << endl;
	cout << min(tmp1, tmp2) << " " << 1;
}

int process(long long a, long long b)
{
	long long ucln = gcd(a, b);
	long long bcnn = (a * b) /  ucln;
	long long tmp1 = cnt_primeuoc(min(a, b)) + cnt_primeuoc(max(a, b) / ucln);
	// << cnt_primeuoc(min(inp[1], inp[2]));
	long long tmp2 = cnt_primeuoc(bcnn / a) + cnt_primeuoc(bcnn / b);
	return min(tmp1,tmp2);
}
void sub2()
{
	for(int  i =1; i<=n; i++)
	{
		pair<int, int> res = {1e9, 1e9};
		for(int j = 1; j<=n; j++)
		{
			if(i == j) continue;
			if(process(inp[i], inp[j]) < res.first)
			{
				res.first = process(inp[i], inp[j]);
				res.second = j;
			}
		}
		cout << res.first << " " << res.second << '\n';
	}
}


int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	inp.resize(n+1);
	for(int i =1; i<=n; i++) cin >> inp[i];
	gen_prime();
//	sub1();
sub2();
	return 0;
}