## [URI ONLINE JUDGE] – 1030– Flavious Josephus Legend

The Josephus problem is this way known because of the Flavius Josephus legend, a Jewish historian living in the 1st century. According to Josephus’ account of the siege of Yodfat, he and his 40 comrade soldiers were trapped in a cave, the exit of which was blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. Josephus states that by luck or maybe by the hand of God, he remained the last and gave up to the Romans.”

## Input

There are **NC **(1 ≤ **NC **≤ 30 ) test cases. In each input test case there will be a pair of positive integer numbers **n **(1 ≤ **n **≤ 10000 ) and **k **(1 ≤ **k **≤ 1000). The number **n **represent the quantity of people in the circle, numbered from 1 to **n**. The number **k **represents the size of step between two men in the circle.

Follow an example with 5 men and step 2: In this example the remaining element is 3.

The data must be read from standard input.

## Output

For each test case we will have a line of output, presenting the in the following format:* Case n: m* always with a space before

**n**and

**m**.

Sample Input | Sample Output |

3 5 2 6 3 1234 233 | Case 1: 3 Case 2: 1 Case 3: 25 |

my solution:

[code language=”cpp”]

#include <iostream>

#include <vector>

using namespace std;

int josephus(int n, int k){

if (n == 1) return 1;

return ((josephus(n – 1, k) + k – 1) % n) + 1;

}

int main(){

unsigned int k, n;

int c, q;

cin >> q;

c = 0;

while (++c <= q){ cin >> n >> k;

cout << "Case " << c << ": " << josephus(n, k) << endl;

}

return 0;

}

[/code]