P16911 [JLCPC 2026] Manhattan Cycle

Little G is an intelligent lifeform living on planet $\mathbf{H}$. On this planet, there are endless flower fields, and Little G really likes jumping around in them. On the $(10^9+7)$-th day of playing in the flowers, Little G learned what Manhattan distance is, and immediately created a game using it. Little G’s game works like this: choose a square flower field, then divide it into $n^2$ identical small squares, arranged so that each row and each column has $n$ squares. Little G jumps between the vertices of these squares. For each jump, the distance between the start point and the end point must be a given positive integer $K$. Also, Little G does not want to get lost and be unable to find home, so Little G wants to return to the starting point after some number of jumps. Little G immediately found a simple plan. Specifically, Little G first chooses a corner point as the start, then chooses a point whose Manhattan distance to that corner is $K$, jumps there, and then jumps back. Using this method, Little G immediately found all solutions with an even number of jumps. However, Little G thinks this is too simple. He wants to find more powerful plans, so he asks you for help, hoping you can help him find some solutions with an odd number of jumps. Based on previous experience, Little G believes that as long as he finds a plan with the smallest number of jumps, he can construct plans with more jumps. Therefore, you only need to output, among all solutions with an odd number of jumps, the minimum number of jumps, or answer that such a solution does not exist. Moreover, since Little G has not yet decided how many parts to divide the flower field into, nor the jumping distance, he will ask you $T$ times. Each time he gives positive integers $n, K$, and you need to answer all his queries in order. To help you humans understand the mysterious thoughts of intelligent life on planet $\mathbf{H}$, we can view all vertices after the division as points in the Cartesian coordinate system whose $x$- and $y$-coordinates are both integers and lie in $[0,n]$. We call such points special points. The condition for being able to jump between two special points $\mathbf{I}(x_1,y_1),\mathbf{T}(x_2,y_2)$ is $|x_1-x_2|+|y_1-y_2|=K$. For a query with given positive integers $n, K$, Little G wants the following answer: whether there exists a plan that starts from some special point, jumps between special points according to the rules above, and finally returns to the starting point, with an odd number of jumps. If such a plan exists, output the minimum number of jumps among all such plans; otherwise, output $-1$.

The first line contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases. The next $T$ lines each describe one test case. Each test case contains two integers $n$ and $K$ ($1 \le n \le 10^8$, $1 \le K \le 2n$).

For each test case, output one integer per line. If there exists a jumping plan with an odd number of steps, output the minimum number of jumps among all such plans; otherwise output $-1$, meaning there is no solution.

Translated by ChatGPT 5