/*      EXP OJI 2004 Clasa a 9 a    */

#include<stdio.h>
#include<math.h>
#define N 6010
#define K 30010

int x[N], p[N], y[N], f[N];
char v[K];
int m, n, dp, i, k, j;
char sw;

void scan(){
    int i;
    freopen("exp.in","r",stdin);
    freopen("exp.out","w",stdout);
    scanf("%d",&m);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
        scanf("%d",&x[i]);
    fclose(stdin);
}

void ciur(){
    int i,j;
    v[0]=1;
    v[1]=1;
    p[1]= 2;
    dp=1;
    for (i=4;i<=K;i+=2)
        v[i]=1;
    for (i=3;i<=K;i+=2){
        if (v[i]==0){
            ++dp;
            p[dp]=i;
            for (j=i+i;j<=K;j+=i)
                v[j]=1;
        }
    }
}


void solve(){
    for (i=1;i<=dp;++i)
        f[i]= 0;
    for (i=1;i<=n;++i){
        j= 1;
        while (x[i]!=1){
            while (x[i]%p[j]==0){
                ++f[j];
                x[i]/=p[j];
            }
            ++j;
        }
    }
    sw=1;
    for (i=1;i<=dp && sw==1;++i)
        if (f[i]%m!=0)
            sw=0;
}

void print(){
    if (sw==0)
        printf("0\n");
    else{
        printf("%d\n",1);
    for (i=1;i<=dp;++i)
        if (f[i]>0)
            printf("%d %d\n",p[i],f[i]/m);
    }
    fclose(stdout);
}

int main(){
    scan();
    ciur();
    solve();
    print();
    return 0;
}