#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	while (Q--) {
		int u, v;
		cin >> u >> v;
		if (N == 1) {
			cout << min(u, v) << endl;
			continue;
		}
		vector<int> x, y;
		while (u > 0) {
			x.push_back(u);
			u = (u + N - 2) / N;
		}
		while (v > 0) {
			y.push_back(v);
			v = (v + N - 2) / N;
		}
		reverse(y.begin(), y.end());
		for (auto val : x) {
			if (binary_search(y.begin(), y.end(), val)) {
				printf("%d\n", val);
				break;
			}
		}
	}
	return 0;
}