#include<bits/stdc++.h>
#define LL long long
#define bp __builtin_parity
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e7+5,NN=1e5+5,mod=998244353;
int n,m,pr[N/10],mu[N],mn[N],tot,a[35];LL c[NN];bool v[N];
inline int md(int x){return x>=mod?x-mod:x;}
inline void ad(int &x,int y){x=md(x+y);}
inline void init(int M)
{
	for(int i=2;i<=M;i++)
	{
		if(!v[i]) pr[++pr[0]]=i,mn[i]=i,mu[i]=-1;
		for(int j=1;j<=pr[0]&&i*pr[j]<=M;j++)
		{
			v[i*pr[j]]=1;mn[i*pr[j]]=mn[i];
			if(i%pr[j]==0) break;mu[i*pr[j]]=-mu[i];
		}
	}fill(v+1,v+1+M,0);
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;init(n);
	while(m--)
	{
		int u,v;LL ans=0,t;cin>>u>>v;
		if(__gcd(u,v)==1){cout<<"1 1\n";continue;}
		ans+=__gcd(u,v)==2;
		for(int p;u^1;){p=mn[u],a[tot++]=p,::v[p]=1;while(!(u%p)) u/=p;}
		for(int p;v^1;){p=mn[v];if(!::v[p]) a[tot++]=p;while(!(v%p)) v/=p;}
		c[0]=1;for(int i=1,B;i<(1<<tot);i++) B=__lg(i),c[i]=c[i-(1<<B)]*a[B];
		for(int i=0,k;i<(1<<tot);i++) t=n/c[i],ans+=(bp(i)?-t:t);
		cout<<"2 "<<ans<<"\n";
		for(int i=0;i<tot;i++) ::v[a[i]]=0;
	}
	return 0;
}