The objective of this problem is to test the students’ understanding on Circular Linked List.
Problem Description
Josephine is a beautiful princess. She's so beautiful that there are N princes proposing to her (needless to say, N could be as large as 100). After lots of consideration, Josephine and her parents realized that all these princes are perfect, so that it is impossible to choose one and reject the others with a good reason. They decided that Josephine would not reject the one chosen by Fate, while other princes could not ask for a fairer decision.
N princes, numbered from 1..N, are asked to stand in a circle. Our beautiful princess would choose a random number K and begin to find her fiancé with that number. Starting from the first person, she counted to K, and removed that K-th person from the circle. Then, she starts counting from the next person and removes the K-th person. This process is repeated until all candidates are removed but The Chosen One.
Everything has been prepared, except one minor problem. To be sure that the processes are random enough, Josephine chose a large number K (around 100). As the result, counting and removing one princess after another would be a painful process. She leaves this work to you – the Royal Programmer.
Given N and K, your program should print out the numbers of princes in the order that they are removed from the circle. The last number would be The Chosen One.
Input
The first line consist of T, the number of test cases, T <= 100. The following T lines describe T test cases, each line containing two integers, N and K.
Output
One line for each test case consists of princes’ numbers in the indicated order. For each output number, it is followed by a whitespace.
Sample Input Sample Output
2 1 2 3
3 1 2 4 3 1
4 2
Explanation
Test case 1:
Starting from 1. Stop and remove 1.
Starting from 2. Stop and remove 2.
Only 3 is left as The Chosen One.
Test case 2:
Starting from 1, count to 2. Stop and remove 2.
Starting from 3, count to 4. Stop and remove 4.
Starting from 1, count to 3. Stop and remove 3.
Only 1 is left as The Chosen One.
0
