Eeny Meeny Moo

너무 많은 사람이 동시에 인터넷을 사용하면 네트워크가 아주 느려진다는 것을 경험해 본 적이 있을 것입니다.

이 문제를 해결하기 위해 울름 대학교(University of Ulm)는 부하가 몰리는 시간대에 일부 도시의 인터넷 접속을 체계적이고 공정하게 차단하는 방식을 고안했습니다. 나라의 도시들은 완전히 무작위 순서로 $1$번부터 $n$번까지 번호가 매겨져 있습니다. 프라이부르크가 $1$번, 울름이 $2$번, 카를스루에가 $3$번, 이런 식입니다.

그런 다음 수 $m$을 하나 고릅니다. 먼저 $1$번 도시의 접속을 차단하고(가장 공정한 시작점입니다), 그다음부터는 아직 연결되어 있는 도시만 세면서 $n$번 다음에는 다시 $1$번으로 돌아오도록 순환하며 매 $m$번째 도시를 차례로 차단합니다. 예를 들어 $n = 17$, $m = 5$이면 도시들은 [1, 6, 11, 16, 5, 12, 2, 9, 17, 10, 4, 15, 14, 3, 8, 13, 7] 순서로 차단됩니다.

가장 뛰어난 프로그래머들이 사는 울름($2$번 도시)이 가장 오래 연결을 유지하는 것이 공정하므로, $2$번 도시가 가장 마지막에 차단되도록 $m$을 정해야 합니다.

$n$이 주어졌을 때, $2$번 도시가 마지막으로 차단되게 하는 가장 작은 정수 $m$을 구하는 프로그램을 작성하세요.

입력은 한 줄 이상으로 이루어집니다. 각 줄에는 도시의 수를 나타내는 정수 $n$이 하나씩 주어지며 $3 \le n < 150$입니다. 입력은 $0$이 주어지는 줄로 끝나며, 이 줄은 처리하지 않습니다.

각 $n$에 대해, $2$번 도시가 가장 마지막에 차단되게 하는 가장 작은 정수 $m$을 한 줄에 하나씩 출력하세요.