#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
template<typename T>inline void ckmax(T &x,T y){x=x<y?y:x;}
template<typename T>inline void ckmin(T &x,T y){x=x>y?y:x;}
template<typename T=int>inline T read(){
    T res=0,f=1; char k;
    while(!isdigit(k=getchar())) if(k=='-') f=-1;
    while(isdigit(k)) res=res*10+k-'0',k=getchar();
    return res*f;
}
template<typename T>inline void print(T x,bool fl=1){
    if(x<0) putchar('-'),x=-x; 
    if(x>=10) print(x/10,0);
    putchar(x%10+'0');
    if(fl) putchar('\n');
}
int n,q;
const int N=1e7+10;
int pri[N],d[N],cnt;
int pp[20],vv[1<<12];
bool isc[N];
signed main(){
    for(int i=2;i<=1e7;++i){
        if(!isc[i]) pri[++cnt]=i,d[i]=i;
        for(int j=1;i<=1e7/pri[j]&&j<=cnt;++j){
            d[i*pri[j]]=pri[j];
            isc[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
    n=read(); q=read();
    for(int eee=1;eee<=q;++eee){
        int u=read(),v=read();
        if(gcd(u,v)==1){
            puts("1 1");
            continue;
        }
        int ans=n;
        set<int> pr;
        int tmp=u;
        while(tmp!=1) pr.insert(d[tmp]),tmp/=d[tmp];
        tmp=v;
        while(tmp!=1) pr.insert(d[tmp]),tmp/=d[tmp];
        int cnt=0;
        for(auto v:pr) pp[cnt++]=v;
        vv[0]=1;
        for(int s=1;s<(1<<cnt);++s){
            int lb=s&(-s);
            vv[s]=vv[s^lb]*pp[__builtin_ctz(lb)];
            if(__builtin_popcount(s)&1) ans-=n/vv[s];
            else ans+=n/vv[s];
        }
        if(gcd(u,v)==2) ++ans;
        printf("2 %d\n",ans);
    }
    return 0;
}