POCRI - Power Crisis

no tags 

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

hide comments
Miguel Angel Diaz: 2013-01-07 22:44:47

Hmm. I precomputed values from 13-100 and put them in an array; yet, I am getting WA. Why?

Aradhya: 2012-03-28 11:30:39

awe$0me question!!

nblt: 2012-03-11 03:51:32

What's the meaning of the problem?

Garima Sachan: 2012-01-26 21:07:41

@Sachin Gupta ans is correct... read problem statement again..

Sachin Gupta: 2012-01-26 13:24:31

in the question explanation the ans for N=17 is 5 but in sample output it is 7 :D

BOND: 2011-12-24 00:49:38

for those getting WA..
hint : take care of the limit of the loop :)

Last edit: 2012-01-05 17:05:30
Al: 2011-10-22 07:15:42

I also got this to work on UVA, but not here. Is there still an issue?

abcdef: 2011-07-12 14:26:35

getting TLE!!!! any method to solve....
pls help......

Problem Solver: 2011-07-10 14:57:09

don't read to EOF... read until 0 appear... this gave me AC

Michael T: 2011-07-04 15:24:21

@Kashyap: Input


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