#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
//define int __int128

using namespace std;

typedef pair<int,int> PII;
typedef long long int llint;
const llint mod=998244353;
const int inf=0x3f3f3f3f;
const llint INF=0x3f3f3f3f3f3f3f3f;
inline int read(){
    int ans=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ans=ans*10+ch-'0';ch=getchar();}
    return ans*w;
}

inline llint qpow(llint a,llint b){
    llint ans=1;
    a%=mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

bool nop[10000005]={0};
int n,q,pri[700000],cnt=0;

inline void init(){
    nop[0]=nop[1]=1;
    for(int i=2;i<=n;i++){
        if(!nop[i]){
            pri[cnt++]=i;
        }
        for(int j=0;j<cnt&&pri[j]*i<=n;j++){
            nop[pri[j]*i]=1;
            if(i%pri[j]==0) break;
        }
    }
}
bool vis[700000];
inline void solve(){
    n=read(),q=read();
    init();
    while(q--){
        int u=read(),v=read();
        if(__gcd(u,v)==1){
            printf("1 1\n");
        }
        else{
            llint tmp=n;
            memset(vis,0,sizeof(bool)*cnt);
            for(int j=0;j<cnt&&pri[j]*pri[j]<=u;j++){
                if(u%pri[j]==0){
                    while(u%pri[j]==0){
                        u/=pri[j];
                    }
                    tmp=tmp*(pri[j]-1)/pri[j];
                    vis[j]=1;
                }
            }
            for(int j=0;j<cnt&&pri[j]*pri[j]<=v;j++){
                if(v%pri[j]==0){
                    while(v%pri[j]==0){
                        v/=pri[j];
                    }
                    if(!vis[j]) tmp=tmp*(pri[j]-1)/pri[j],vis[j]=1;
                }
            }
            if(u>1){
                int j=lower_bound(pri,pri+cnt,u)-pri;
                if(!vis[j]) tmp=tmp*(pri[j]-1)/pri[j],vis[j]=1;
            }
            if(v>1){
                int j=lower_bound(pri,pri+cnt,v)-pri;
                if(!vis[j]) tmp=tmp*(pri[j]-1)/pri[j],vis[j]=1;
            }
            printf("2 %lld\n",tmp);
            //for(int i=0;i<cnt;i++) if(!vis[i]) printf("%d\n",pri[i]);
        }
    }

}

int main()
{
    //IO;
    int tt=1;
    //tt=read();
    //cin>>tt;
    while(tt--){
        solve();
    }
}


/*
struct D{
    int to,next;
}edge[200005];
int head[100005]={0},tot=1;
inline void adde(int u,int v){
    edge[tot]={v,head[u]};
    head[u]=tot++;
}
*/
/*
void print(__int128 x)
{
    if(x>=10)
    {
        print(x/10);
        cout << (int)(x%10);
    }
    if(x<10)
    {
        cout << (int)(x);
        return ;
    }
}
*/