#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 10202000
using namespace std;
const int mo=998244353;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int mn[N],pre[N],tot,f[N],a[1002];
signed main(){
	int n=read(),Q=read();
	mn[1]=1; 
	for (int i=2;i<=n;++i){
		if (!f[i])mn[pre[++tot]=i]=i;
		for (int j=1;j<=tot&&pre[j]*i<=n;++j){
			f[i*pre[j]]=1;
			if (i%pre[j])
				mn[i*pre[j]]=min(mn[i],pre[j]);
			else{
				mn[i*pre[j]]=mn[i];
				break;
			}
		}
	}
	while (Q--){
		int u=read(),v=read(),uu=u,vv=v;
		if (__gcd(u,v)==1){puts("1 1");continue;}
		printf("2 ");
		int ans=0,tot=0;
		for (;u>1;u/=mn[u])a[++tot]=mn[u];
		for (;v>1;v/=mn[v])a[++tot]=mn[v];
		sort(a+1,a+1+tot);
		tot=unique(a+1,a+1+tot)-a-1;
		for (int s=0;s<(1<<tot);++s){
			int cnt=0,t=n;
			for (int i=1;i<=tot;++i)
				if (s&(1<<i-1))
					++cnt,t/=a[i];
			(ans+=(cnt&1?-1:1)*t)%=mo;
		}
		printf("%d\n",(ans+(__gcd(uu,vv)==2)+mo)%mo);
	}
    return 0;
}