题目描述

“数字轮盘”是一款益智游戏，基于一个带有指针的圆形轮盘展开。轮盘边缘按顺时针刻有数字 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 \leq T \leq 10^2$，$2 \leq N \leq 500$，$0 \leq K \leq 500$。

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