Aku Negaraku

Interview

Time limit3sMemory limit512 MB

Summary

For each N and M, simulate Josephus elimination around a circle and report the last remaining trainee's number.

Level: Medium4 of 10
Topics: Simulation, Array, Recursion
Solved: No attempts yet

Problem

An international leadership training academy in Kuala Lumpur sends thousands of trainees to companies around the world every year. For a fair selection, $N$ trainees numbered from $1$ to $N$ stand in a circle.

A number $M$ is picked at random. Counting starts at trainee $1$ , and every $M$ -th person among those not yet selected is picked, wrapping around from $N$ back to $1$ and skipping trainees who have already been picked. The last trainee remaining after all others have been picked stays in Malaysia. Find the number that stays in Malaysia.

Input

The input consists of multiple lines. Each line contains $N$ , the number of trainees, and $M$ , the step size, with $1 \le N \le 1500$ and $1 \le M \le 50$ . The last line contains 0 0 and must not be processed.

Output

For each line of input, print the number that stays in Malaysia according to the scheme above.

Examples1

Example 1
Input
```
15 6
550 23
0 0
```
Expected output
```
7
470
```