#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,M=15,NN=1e3+5,mod=998244353;
int n,m,pr[N/10],mu[N],mn[N],t1,a[M],t2,b[M],c[NN],d[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];
		}
	}
}
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;u/=__gcd(u,v);t1=t2=0;
		for(int p;u^1;){p=mn[u],a[t1++]=p;while(!(u%p)) u/=p;}
		for(int p;v^1;){p=mn[v],b[t2++]=p;while(!(v%p)) v/=p;}
		c[0]=1;for(int i=1,B;i<(1<<t1);i++) B=__lg(i),c[i]=c[i-(1<<B)]*a[B];
		d[0]=1;for(int i=1,B;i<(1<<t2);i++) B=__lg(i),d[i]=d[i-(1<<B)]*b[B];
		for(int i=0,k;i<(1<<t1);i++) for(int j=0;j<(1<<t2);j++)
			t=n/(1ll*c[i]*d[j]),ans+=((bp(i)^bp(j))?-t:t);
		cout<<"2 "<<ans<<"\n";
	}
	return 0;
}