Little G is an intelligent being living on planet $$$\mathbf{H}$$$. On this planet, there are endless fields of flowers, and Little G loves hopping among them. On the $$$(10^9+7)$$$-th day of playing in the flower fields, Little G learned about Manhattan distance and immediately invented a game with it.

Little G's game works as follows: choose a square patch of flowers and divide it into $$$n^2$$$ identical smaller squares arranged in $$$n$$$ rows and $$$n$$$ columns, then hop between all the vertices of these squares. Each hop must cover a Manhattan distance of exactly a given positive integer $$$K$$$. Moreover, Little G does not want to get lost, so he wants to eventually return to the starting point after a sequence of hops.

Little G quickly found a simple solution: start at a corner vertex, hop to a vertex at Manhattan distance $$$K$$$, and hop back. This immediately gives all solutions with an even number of hops. But Little G thinks this is too easy — he wants to find solutions with an odd number of hops, and asks for your help.

Based on his experience, Little G believes that finding the minimum number of hops is sufficient to construct solutions with more hops. So you only need to report the minimum number of hops among all solutions with an odd number of hops, or report that no such solution exists. Since Little G has not yet decided on $$$n$$$ or $$$K$$$, he will ask you $$$T$$$ queries, each specifying positive integers $$$n$$$ and $$$K$$$.

To help you (a human) better understand the mysterious ideas of planet $$$\mathbf{H}$$$'s inhabitants: consider all vertices of the divided squares as lattice points in the Cartesian plane with both coordinates being integers in $$$[0, n]$$$. We call these special points. A hop between two special points $$$\mathbf{I}(x_1,y_1)$$$ and $$$\mathbf{T}(x_2,y_2)$$$ is valid if and only if $$$|x_1-x_2|+|y_1-y_2|=K$$$.

For each query with given positive integers $$$n$$$ and $$$K$$$: determine whether there exists a cycle starting and ending at some special point, following the hopping rules, with an odd number of hops. If such a cycle exists, output the minimum number of hops; otherwise, output $$$-1$$$.