let () = Scanf.scanf "%d %d\n" @@ function
  | 1 -> fun q ->
      for i = 0 to q - 1 do
        Printf.printf "%d\n" @@ Scanf.scanf "%d %d\n" min
      done
  | n -> fun 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
