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

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