#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int N = 1e7 + 10;
int vis[N], a[N], n, q;
vector<int> p, ve;
ll ans;

void init()
{
	vis[0] = vis[1] = 1;
	_for(i, 2, 1e7)
	{
		if(!vis[i]) a[i] = i, p.push_back(i);
		for(int x: p)
		{
			if(x * i > 1e7) break;
			vis[x * i] = 1;
			a[x * i] = x;
			if(i % x == 0) break;
		}
	}
}

vector<int> deal(int x)
{
	vector<int> res;
	while(x > 1)
	{
		int t = a[x];
		res.push_back(t);
		while(x % t == 0) x /= t;
	}
	return res;
}

void dfs(int i, int cnt, ll cur)
{
	if(i == ve.size())
	{
		if(cur > 1)
		{
			if(cnt % 2 == 1) ans += n / cur;
			else ans -= n / cur;
		}
		return;
	}
	dfs(i + 1, cnt + 1, cur * ve[i]);
	dfs(i + 1, cnt, cur);
}

int gcd(int a, int b) { return !b ? a: gcd(b, a % b); }

int main()
{
	init();

	scanf("%d%d", &n, &q);
	while(q--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		vector<int> pu = deal(u), pv = deal(v);

		ve = pu;
		for(int x: pv) ve.push_back(x);
		sort(ve.begin(), ve.end());
		ve.erase(unique(ve.begin(), ve.end()), ve.end());

		if(ve.size() == pu.size() + pv.size())
		{
			puts("1 1");
			continue;
		}

		ans = 0;
		dfs(1, 1, ve[0]);
		dfs(1, 0, 1);
		printf("%d %lld\n", 2, n - ans + (gcd(u, v) == 2));
 	}
	
	return 0;
}