
let () = Scanf.scanf "%d %d\n" @@ fun n q ->
  let up v = (v - 1) / n in
  let rec upn v = function
    | 0 -> v
    | n -> upn (up v) (n - 1) in
  let rec depth acc = function
    | 0 -> acc
    | v -> depth (1 + acc) (up v) in
  let depth = depth 0 in
  let rec lca v w =
    if v = w then v
    else lca (up v) (up w) in
  let lca v w =
    let dv = depth v in
    let dw = depth w in
    if dv <= dw
    then lca v (upn w (dw - dv))
    else lca (upn v (dv - dw)) w in
  for i = 0 to q - 1 do
    Scanf.scanf "%d %d\n" @@ fun v w ->
      Printf.printf "%d\n" @@ succ @@ lca (v - 1) (w - 1)
  done

