挖坑

题号：NC259240
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出一个整数 $n$ ，表示一张 $3\times n$ 的地图，左上角为 $(1,1)$ ，右下角为 $(3,n)$ 。小明从左上角走到右下角，每一步可以往上下左右四个相邻方向移动，例如 $(i,j)$ 可以走到 $(i+1,j),(i-1,j),(i,j-1),(i,j+1)$ 其中之一。

现在可以选择在地图某些地方挖坑，如果选择 $(i,j)$ 挖坑，则小明不能经过 $(i,j)$ 这个点。

每次询问给出一个整数 $k$ ，问：至少要挖几个坑，才能使得小明从 $(1,1)$ 到 $(3,n)$ 的最少步数等于 $k$ ，如果无论如何都不能等于 $k$ ，输出 $-1$ 。

第一行包含一个整数 $q\ (1\le q\le10^6)$ ，表示询问个数。

接下来 $q$ 行，每行包含两个整数 $n\ k\ (1\le n,k\le10^9)$ ，含义和题目描述一致。

输出  行，每行一个整数 ，表示最小挖坑数。

示例1

复制

2
3 4
5 10

复制

0
4

询问 $1$ ，不需要挖坑，最短距离就是 $4$ 。

询问 $2$ ，其中一种最少挖坑方案为 $\left(\begin{array}{}0&1&0&0&0\\0&1&0&1&0\\0&0&0&1&0\end{array}\right)$ ， $1$ 表示坑，最少挖 $4$ 个坑。