Eeny Meeny Moo

You have surely experienced that when too many people use the Internet at the same time, the network becomes very, very slow.

To put an end to this, the University of Ulm devised a fair emergency scheme for times of peak load that cuts off Internet access for some cities in a systematic way. The country's cities are numbered from $1$ to $n$ in a purely random order: Freiburg is city $1$, Ulm is city $2$, Karlsruhe is city $3$, and so on.

A number $m$ is then chosen. Internet access is first cut off in city $1$ (clearly the fairest starting point). After that, counting only the cities that are still connected and wrapping around from city $n$ back to city $1$, every $m$-th city is cut off in turn. For example, if $n = 17$ and $m = 5$, access is cut off in the order [1, 6, 11, 16, 5, 12, 2, 9, 17, 10, 4, 15, 14, 3, 8, 13, 7].

Because it is only fair that Ulm — home of the best programmers — keeps its connection the longest, $m$ must be chosen so that city $2$ is the very last city to be cut off.

Given $n$, write a program that finds the smallest integer $m$ for which city $2$ is cut off last.

The input consists of one or more lines. Each line contains a single integer $n$ with $3 \le n < 150$, the number of cities in the country. The input ends with a line containing $0$, which is not processed.

For each value of $n$, print a single line containing the smallest integer $m$ that makes city $2$ the last city to be cut off.