"I need a quote here."

igor

There are n chairs in a row at the doctor's office. Starting at 8:00, n patients will arrive, one every 5 minutes, and sit down on a chair. Each patient has a different sickness and does not want to sit next to any other patient. After the last patient takes his seat, the receptionist tells everybody that the doctor is sick, and the office is closed for the day. At this time, everybody stands up and leaves.

There are two types of patients:

• Pessimists are always sure that the next patient who comes into the office will sit next to them.
• Optimists think that all the patients who arrive after them are optimists, too, and think in the same way.

Each patient is a mathematician and will always pick a chair that will minimize the time spent sitting next to another patient. If there is a tie, the patient will pick the leftmost chair among the best ones. Optimists know this fact.

Input
The first line of input gives the number of cases, N. N test cases follow. Each one consists of two lines. The first line has n (0<n<5000) and k (1 <= k <= n). Assume that every k'th patient is an optimist, and all others are pessimists.

Output
For each test case, output the number of the chair on which the last patient will sit, counting from the left, starting with 1.

5
1 1
2 1
2 2
5 1
5 2

Case #1: 1
Case #2: 2
Case #3: 2
Case #4: 4
Case #5: 4

In case 4, all patients are optimists, and they will pick the 5 chairs in the order 5, 1, 3, 2, 4.

In case 5, patients 1, 3 and 5 are pessimists, and patients 2 and 4 are optimists. They will pick the chairs in the order 1, 5, 3, 2, 4.