So it is known that there is one popular game of Chinese girls. N girls stand forming a circle and throw a ball to each other. First girl holding a ball throws it to the K-th girl on her left (1 ≤ K ≤ N/2). That girl catches the ball and in turn throws it to the K-th girl on her left, and so on. So the ball is passed from one girl to another until it comes back to the first girl. If for example N = 7 and K = 3, the girls receive the ball in the following order: 1, 4, 7, 3, 6, 2, 5, 1.
To make the game even more interesting the girls want to choose K as large as possible, but they want one condition to hold: each girl must own the ball during the game.