#include <iostream>
#include <algorithm>
using namespace std;

int n, q;
int a, b;

int p(int x) { return (x + n - 2) / n; }

int main() {
	cin >> n >> q;
	for (int i = 0; i < q; i++) {
		cin >> a >> b;
		
		if (n == 1) { cout << min(a, b) << endl; }
		
		else {
			while (a != b) {
				if (a > b) a = p(a);
				else b = p(b);
			}
			cout << a << endl;
		}
	}
	return 0;
}