题目描述

“数字轮盘”是一款益智游戏，基于一个带有指针的圆形轮盘展开。轮盘边缘按顺时针刻有数字 1 至 N，初始时指针指向 1。

游戏分为两阶段：旋转轮盘和恢复轮盘。

第一阶段，将轮盘顺时针旋转 K 次。每次旋转，数字依次后移一位，指针指向的数字随之改变。例如，对于 N=4 的轮盘，初始状态为 1, 2, 3, 4（指针指向 1），旋转一次变为 4, 1, 2, 3（指针指向 4），再旋转一次变为 3, 4, 1, 2（指针指向 3），依此类推。

第二阶段，小蓝需通过操作恢复初始状态，每次操作包含以下两步：

第一步：翻转以指针为起点、顺时针方向的前 N−1 个数字的顺序。 第二步：翻转除指针外的 N−1 个数字的顺序。 例如，对 N=4，状态为 4, 1, 2, 3（指针指向 4）进行一次操作：

第一步：翻转 4, 1, 2，变为 2, 1, 4, 3（指针指向 2）。 第二步：翻转 1, 4, 3，变为 2, 3, 4, 1（指针指向 2）。 现在，给定轮盘的数字个数 N 和旋转次数 K，请计算小蓝最少需要几次操作才能恢复初始状态。如果无法恢复初始状态，则输出 -1。

输入格式

输入的第一行包含一个整数 T，表示测试用例的数量。

接下来 T 行，每行包含两个整数 N 和 K，分别表示轮盘上的数字个数和旋转次数。

输出格式

输出共 T 行，每行包含一个整数，表示最少需要的操作次数。如果无法恢复初始状态，则输出 −1。

样例

2
3 2
4 1

2
-1

说明/提示

【评测用例规模与约定】

对于 30% 的评测用例，$1≤T≤10^2$，$2≤N≤500$，$0≤K≤500$。

对于 100% 的评测用例，$1≤T≤10^5$，$2≤N≤10^9$，$0≤K≤10^9$。