352. Josephus problem

0

Easy

Given the total number of people

**n**and a number**k**which indicates that**k-1**people are skipped and the**kth**person is killed in a circle in a fixed direction. The task is to determine the safest position in the circle so that when you perform these operations starting from the 1st position in the circle, you are the last one remaining and survive.Input Format

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains 2 integers n and k.

Output Format

For each test case, output the safest position that satisfies the above condition in a new line.

Example

Input

2
3 2
5 3

Output

3
4

Constraints

1 <= T <= 100
1 <= k, n <= 20

Loading...

View Submissions

Console