POCRI - Power Crisis

During the power crisis in New Zealand this winter (caused by a shortage of rain and hence low levels in the hydro dams), a contingency scheme was developed to turn off the power to areas of the country in a systematic, totally fair, manner. The country was divided up into N regions (Auckland was region number 1, and Wellington number 13). A number, m, would be picked 'at random', and the power would first be turned off in region 1 (clearly the fairest starting point) and then in every m'th region after that, wrapping around to 1 after N, and ignoring regions already turned off. For example, if N = 17 and m = 5, power would be turned off to the regions in the order:1, 6, 11, 16, 5, 12, 2, 9, 17, 10, 4, 15, 14, 3, 8, 13, 7.

The problem is that it is clearly fairest to turn off Wellington last (after all, that is where the Electricity headquarters are), so for a given N, the 'random' number m needs to be carefully chosen so that region 13 is the last region selected.

Write a program that will read in the number of regions and then determine the smallest number m that will ensure that Wellington (region 13) can function while the rest of the country is blacked out.

Input

Input will consist of a series of lines, each line containing the number of regions (N) with 13 <= N < 100. The file will be terminated by a line consisting of a single 0.

Output

Output will consist of a series of lines, one for each line of the input. Each line will consist of the number m according to the above scheme.

Example

Input:
17
0

Output:
7

Added by:Andres Tellez
Date:2011-05-17
Time limit:3.381s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2011-06-05 21:20:31 Santiago Palacio
You gotta be kidding me, actually submitting nothing works! that should not happen!

Last edit: 2011-06-05 21:20:44
2011-06-04 17:28:36 Gaurav
and still test cases are very weak.......or i would say no test cases...
2011-06-04 17:27:00 Gaurav
how is the ans for the exmpl is 7??
why not 5??
1 8 15 5 12 2 9 16 7 13.....13 comes b4 all other numbers are accessed..
2011-06-01 11:50:23 Anuj Arora
if N is 14, then I dont think there is any m present for which the last power off could be done for 13. Am I missing something? In that case, what should we output?
2011-06-01 11:38:43 Anuj Arora
@cegprakash
10 is fine. I think you have missed one line in the problem. The region who are already powered off, will not be consider again for power off. I hope, by this you can get the problem right now.
2011-05-31 04:28:21 ~
plzz add test file..............what is the use of problem!!
2011-05-30 18:53:40 !
Empty submission is also getting correct answer..

Last edit: 2011-05-30 18:54:32
2011-05-30 10:53:53 hendrik
Indeed. Empty submissions get AC! Must be fixed and all submissions rejudget.

Last edit: 2011-05-30 10:54:27
2011-05-29 14:54:30 WARush
Problem setter please add test files,
got acc for just a empty program.
2011-05-28 23:50:26 Alex Anderson
You say the data set is weak. Can an empty file really be weak? There aren't any tests at all.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.