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:

#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; }