local n, q = io.read("*n", "*n")
for i = 1, q do
  local v, w = io.read("*n", "*n")
  while v ~= w do
    if v < w then
      w = (w + n - 2) // n
    else
      v = (v + n - 2) // n
    end
  end
  print(v)
end
