#include <bits/stdc++.h>

using namespace std;
int hfac(long a)
{
    long num=-1;
    for(long i=2;i<=a/2;i++)
    {
        if(a%i==0)
            num=i;
    }
    if(num==-1)
    {
        if(a%2==0)
            return 2;
        else if(a%a==0) 
            return a;
    }
    else
        return num;
}
long longestSequence(vector <long> a) {
    long sum=0;
    for(int i=0;i<a.size();i++)
    {
        long num=1;
        long q=-1;
        long moves=0;
        long fac=-1;
        while(a[i]>=1)
        {
            if(a[i]==1)
            {
                moves+=num;
                break;
            }
            moves+=(fac!=-1)?num:1;
            fac=hfac(a[i]);
            num*=fac;
            a[i]/=fac;
            cout<<fac<<" "<<num<<endl;
        }
        sum+=moves;
        cout<<sum<<endl<<endl;
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    vector<long> a(n);
    for(int a_i = 0; a_i < n; a_i++){
       cin >> a[a_i];
    }
    long result = longestSequence(a);
    cout << result << endl;
    return 0;
}