program evergrowing_tree
  implicit none
  integer :: n, q, v, w, nv, nw, i
  read(*,*) n, q
  if (n == 1) then
    do i = 1, q
      read(*,*) v, w
      write(*,'(i0)') v
    end do
    stop
  end if
  do i = 1, q
    read(*,*) v, w
    v = v-1
    w = w-1
    nv = depth(v,n)
    nw = depth(w,n)
    do while (nw > nv)
      w = (w-1)/n
      nw = nw-1
    end do
    do while (v /= w)
      v = (v-1)/n
      w = (w-1)/n
    end do
    write(*,'(i0)') v+1
  end do
contains
  integer function depth(v,n)
    integer, intent(in) :: v, n
    integer :: x
    depth = 0
    x = v
    do while (x > 1)
      x = (x-1)/n
      depth = depth+1
    end do
  end
end program evergrowing_tree