#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;

int n, q;

int main() {
	cin >> n >> q;
	for (int i = 0; i < q; ++i) {
		int v, w; cin >> v >> w;
		if (n == 1) {
			cout << min(v, w) << endl;
			continue;
		}
		int dv = 0, dw = 0;
		int vv = v, ww = w;
		while (vv != 1) {
			++dv;
			vv = (vv + n - 2) / n;
		}
		while (ww != 1) {
			++dw;
			ww = (ww + n - 2) / n;
		}
		while (dw > dv) {
			w = (w + n - 2) / n;
			--dw;
		}
		while (v != w) {
			v = (v + n - 2) / n;
			w = (w + n - 2) / n;
		}
		cout << v << endl;
	}
	return 0;
}