#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long ll;

ll modExp(ll base, ll index, ll module){
	ll ret = 1;
	for (; index; index >>= 1){
		if (index & 1)
			ret = ret * base % module;
		base = base * base % module;
	}
	return ret;
}

ll exGcd(ll a, ll b, ll &x, ll &y){
	if (b == 0){
		x = 1;
		y = 0;
		return a;
	}
	ll d = exGcd(b, a % b, x, y), t = x;
	x = y;
	y = t - a / b * y;
	return d;
}

//ax + by = c, minimal non-negtive x
ll linearCongruenceEquation(ll a, ll b, ll c = -1){
	ll x, y, d = exGcd(a, b, x, y);
	if (c < 0)
		c = d;
	if (c % d != 0)
		return -1;
	else{
		b /= d;
		x %= b;
		if (x < 0)
			x += b;
		return x * (c / d) % b;
	}
}

void primeFactor(int number, int &count, int factor[]){
	count = 0;
	for (int i = 2; i * i <= number; ++i)
		if (number % i == 0){
			factor[count++] = i;
			for (; number % i == 0; number /= i);
		}
	if (number > 1)
		factor[count++] = number;
}

int getPrimitiveRoot(int number){
	static int count, factor[20];	
	if (number == 2)
		return 1;
	primeFactor(number - 1, count, factor);
	for (int j, i = 2; i < number; ++i){
		for (j = 0; j < count; ++j)
			if (modExp(i, (number - 1) / factor[j], number) == 1)
				break;
		if (j >= count)
			return i;
	}
	return -1;
}

struct DiscreteLogarithm{
	static const int tableSize = 1E6;
	int prime, root;
	int invs;
	unordered_map<int, int> lst;

	void buildTable(){
		lst.clear();
		int e = 1;
		for (int i = 0; i < prime - 1 && i < tableSize; ++i){
			lst[e] = i;
			e = (ll)e * root % prime;
		}
		invs = modExp(modExp(root, prime - 2, prime), tableSize, prime);
	}

	void init(int tprime, int troot = 0){
		prime = tprime;
		root = troot ? troot : getPrimitiveRoot(prime);
		buildTable();
	}

	int query(int number){
		unordered_map<int, int>::iterator p;
		int e = number % prime;
		for (int i = 0; i < prime; i += tableSize){
			if ((p = lst.find(e)) != lst.end())
				return i + p->second;
			e = (ll)e * invs % prime;
		}
		return -1;
	}

	//solve A^k = B (mod p)
	int query(int A, int B){
		int a = query(A), b = query(B);
		int ret = linearCongruenceEquation(a, prime - 1, b);
		return ret;
	}
}disLog[10];

int main(){
	int cas;
	scanf("%d", &cas);
	for (int casi = 1; casi <= cas; ++casi){
		printf("Case #%d:\n", casi);
		int sum, m;
		int n, fac[20], g[20];
		scanf("%d%d", &sum, &m);
		primeFactor(sum, n, fac);
		for (int i = 0; i < n; ++i){
			disLog[i].init(fac[i]);
		}

		for (int i = 0; i < m; ++i){
			int x, y, ans = -1;
			scanf("%d%d", &x, &y);
			for (int j = 0; j < n; ++j){
				int temp = disLog[j].query(x, y);
				if (temp != -1 && (ans == -1 || ans > temp))
					ans = temp;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}