#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int x,d,m,n,v[30000],i,j,dmax,sw;
ifstream fin("exp.in");
ofstream fout("exp.out");
int main()
{
    fin>>m>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        d=3;
        while(x%2==0)
        {
            v[2]++;
            x=x/2;
        }
        if(d>sqrt(x)) d=x;
        while(x>1)
        {
        while(x%d==0)
        {
        v[d]++;10
1223
123
666
321
7890
2213
312
655
1000
1322
        x=x/d;
        }
        d+=2;
        if(d>dmax) dmax=d;
        }
    }
    if(v[2]!=0&&v[2]%m!=0) sw=1;
    for(i=3;i<=dmax&&sw==0;i=i+2)
        if(v[i]!=0&&v[i]%m!=0) sw=1;
    if(sw==1) fout<<0;
    else
    {
        fout<<1<<"\n";
        if(v[2]!=0) fout<<2<<" "<<v[2]/m<<"\n";
        for(i=3;i<=dmax;i+=2)
            if(v[i]!=0) fout<<i<<" "<<v[i]/m<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}