#include <fstream>
#include <vector>

using namespace std;

ifstream cin("pairs.in");
ofstream cout("pairs.out");

int n;
vector<int> v;
vector<int> f(100005);
vector<int> c(100005);
int maxx = -1;

void citire()
{
    int x;
    cin >> n;

    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        v.push_back(x);
        c[x] = 1;
        maxx = max(maxx, x);
    }
}

void rez()
{
    long long sol;
    int i, j;

    for (i = 2, sol = (long long)(n * (n-1) / 2);
           i <= maxx ; i++)
        if (!f[i])
            for ( j = i ; j <= maxx ; j+=i)
                f[j]++;

    for ( i = 2 ; i * i <= maxx ; i++)
        for ( j = i * i ; j <= maxx ; j += i * i)
            f[j] = 0;

    for(i = 2 ; i <= maxx ; i++)
        cout << i << ' ' << f[i] << '\n';
    cout << '\n';

    for( i = 2 ; i <= maxx ; i++)
        if(f[i] >= 1)
        {
            cout << i << ' ' << f[i] << ' ' << sol << ' ';
            int nr = 0;
            for( j = i ; j <= maxx ; j += i)
                if (c[j])
                    nr++;

            (f[i] & 1) ? sol -= (long long)(nr * (nr - 1) / 2)
                                : sol -= (long long)(nr * (nr - 1) / 2);

            cout << (nr * (nr - 1)) / 2 << ' ' << sol << '\n';
        }

    cout << sol;
}

int main()
{
    citire();
    rez();
    return 0;
}