G. The Squared Thinker
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Furtis is tired of programming. He now devotes his free time to thinking about problems, preferably without having to code his solutions, because he is very lazy. He spends his days making up operations, asking himself questions about them and trying to come up with a satisfying solution. It seems it is the only way to explain how he came up with this problem...

Furtis defines a game on a $$$2 \times M$$$ grid ($$$2$$$ rows and $$$M$$$ columns). In each square you start with the value $$$0$$$. In an operation you can choose a square, subtract $$$1$$$ from it and add $$$1$$$ to its two diagonal neighbors. This can only be done if the two neighbors are within the grid.

Example of two types of allowed operations
Example of two types of operations not allowed

More formally:

  1. If the square $$$a_{1, x}$$$ is chosen and the squares $$$a_{2, x-1}$$$ and $$$a_{2, x+1}$$$ are inside the grid, you assign:
    • $$$a_{1, x} \leftarrow (a_{1, x}-1)$$$
    • $$$a_{2, x-1} \leftarrow (a_{2, x-1}+1)$$$
    • $$$a_{2, x+1} \leftarrow (a_{2, x+1}+1)$$$
  2. If the square $$$a_{2, x}$$$ is chosen and the squares $$$a_{1, x-1}$$$ and $$$a_{1, x+1}$$$ are inside the grid, you assign:
    • $$$a_{2, x} \leftarrow (a_{2, x}-1)$$$
    • $$$a_{1, x-1} \leftarrow (a_{1, x-1}+1)$$$
    • $$$a_{1, x+1} \leftarrow (a_{1, x+1}+1)$$$

Furtis wants to know if it is possible to make all the squares at the same time equal to a given integer value $$$V$$$ and if so, the minimum number of operations necessary to do so.

Naturally, you are not Furtis and you are in a competitive programming contest, so you will have to code the solution...

Input

The first line contains a single integer $$$t$$$ — the number of test cases.

The following $$$t$$$ lines each include two integers ($$$M, V$$$) — the number of columns for a $$$2 \times M$$$ grid and the value $$$V$$$ that you want to obtain in all the cells at the same time.

  • $$$1 \le t \le 2 \cdot 10^5$$$
  • $$$1 \le M \le 10^9$$$
  • $$$1 \le V \le 10^9$$$
Output

For each test case, print on a new line a single integer — the minimum number of operations necessary for all cells to have the same value $$$V$$$ at once. If it is impossible for that case, print -1.

Example
Input
2
3 1
6 3
Output
-1
36