Removal of vertices

★★★★★

3.6

36 votes

Data Structures, Math Basic, Basic Math, Math

Details

Submissions

Discussion

Editorial

Problem

You are given an $N-sided$ polygon where vertices are numbered from 1 to $N$ in clockwise order, You are also given an integer $K$ . You create a vertex-explosion machine that explodes vertex in polygon thereby reducing the size of the polygon. You start with vertex 2. At each step, one of the following operations on the polygon is performed:

If $K > 0$ , then there is no effect of the vertex-explosion machine. Now, $K$ is reduced by 1 and you move to the next available vertex at distance 2 in the clockwise direction.
The vertex is exploded thus reducing the number of sides in the polygon by 1 and you move to the next available vertex at distance 2 in the clockwise direction from the exploded vertex.

Note: Polygon with vertex 2 and 1 exists

For example, if $N = 4$ and $K = 2$ , then the following diagram displays an explanation.

You are required to determine the remaining last vertex.

Input format

The first line contains $T$ denoting the number of test cases.
For each test case, the first line contains integers $N$ and $K$ denoting sides of the polygon and integer respectively.

Output format

Print an integer denoting the last-remaining vertex.

Constraints

$1 \leq T \leq 10$

$3 \leq N \leq 10^{14}$

$1 \leq K \leq 10^{14}$

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

Explanation of Test Case 1: In the given figure

Explanation of Test Case 2:

Here vertex 2 is tried to explode but no effect as K = 1, K reduces by 1 and polygon remains the same. Then vertex at distance 2 from current vertex is chosen in clockwise direction which is vertex 4.
vertex 4 is tried to explode, it gets exploded because K = 0 and polygon size is reduced containing 3 vertices(1,2,4). Then vertex at distance 2 from exploded vertex is chosen in clockwise direction which is vertex 2.
vertex 2 is tried to explode, it gets exploded because K = 0 and polygon size is reduced containing 2 vertices(1,3). Then vertex at distance 2 from exploded vertex is chosen in clockwise direction which is vertex 1.
vertex 1 is tried to explode, it gets exploded because K = 0 and polygon size is reduced containing 1 vertices(3). This is our answer.

Explanation of Test Case 4:

Here vertex 2 is tried to explode but no effect as K = 1, K reduces by 1 and polygon remains the same. Then vertex at distance 2 from current vertex is chosen in clockwise direction which is vertex 1.
vertex 1 is tried to explode, it gets exploded because K = 0 and polygon size is reduced containing 2 vertices(2,3). Then vertex at distance 2 from exploded vertex is chosen in clockwise direction which is vertex 3.
vertex 3 is tried to explode, it gets exploded because K = 0 and polygon size is reduced containing 1 vertex (2). This is our answer.