#include <fstream>
#include <bitset>

using namespace std;

int prime[4000], k, expo[30005],n ,m;
bitset <30005>B;
void Ciur(int n)
{
    int i, j;
    B[1]=1;
    for (i=4; i<=n; i=i+2)
        B[i]=1;
    for (i=3; i*i<=n; i=i+2)
        if (B[i]==0)
           for (j=i*i; j<=n; j=j+2*i)
                B[j]=1;
    prime[1]=2;
    k=1;
    for (i=3; i<=n; i=i+2)
        if (B[i]==0)
            prime[++k]=i;
}
int NrDiv(int n)
{
    int s=0, i;
    for (i=1; i*i<n; i++)
        if (n%i==0) s=s+2;
    if (i*i==n) s++;
    return s;
}
int Cauta()
{   int i;
    for (i=2; i<=30000; i++)
    if (expo[i]>0)
        {   if (expo[i]%m!=0)
                return 0;
            else expo[i]=expo[i]/3;
        }
    return 1;
}
int main()
{
    ifstream fin ("exp.in");
    ofstream fout ("exp.out");
    int i, d, x;
    fin >> m >> n;
    Ciur(30000);
    for (k=1; k<=n; k++)
    {
        fin >> x;
        d=2;
        i=1;
        while (x>1 && d*d<=x)
        {
            while (x%d==0)
            {
                x=x/d;
                expo[d]++;
            }
            i++;
            d=prime[i];
        }
        if (x>1) expo[x]++;
    }
    x=Cauta();
    if (x==0) fout << "0\n";
    else fout << "1\n";
    for  (i=2; i<=30000; i++)
        if (expo[i]>1)
            fout << i << " " << expo[i] << "\n";
    fin.close();
    fout.close();
    return 0;
}