#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9 + 7, MOD = 1e9 + 7;
const long long LINF = 1e18;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};


signed main() {
	int n, q;
	cin >> n >> q;
	while (q--) {
		int v, w;
		cin >> v >> w;
		if (n == 1) cout << min(v, w) << endl;
		else {
			while (v != w) {
				if (v < w) w = (w - 2) / n + 1;
				else v = (v - 2) / n + 1;
			}
			cout << v << endl;
		}
	}
	return 0;
}
