#include<bits/stdc++.h>
#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];
int 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();
while(q--){
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);
}
for(int i=1;i<=n;++i)
return 0;
}