import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

int N;

int solve(int x) {
    if (x == 0)
        return 0;
    int q = x % N;
    if (q == 0) q = N;
    return (x-q)/N;
}

void main() {
    auto s = readln.split.map!(to!int);
    N = s[0];
    auto Q = s[1];

    while (Q--) {
        s = readln.split.map!(to!int);
        auto v = s[0]-1;
        auto w = s[1]-1;
        while (v != w) {
            if (v > w)
                v = solve(v);
            else
                w = solve(w);
        }
        writeln(v+1);
    }
}
