题目描述

你被困在一个密室中，面前有一个控制面板，上面有 $n$ 个开关，控制着密室中的 $m$ 盏灯。开关编号为 $0, 1, \dots, n - 1$，灯编号为 $0, 1, \dots, m - 1$。

开关与灯的作用规则如下：

• 按下第 $i$ 个开关（$0 \leq i < n$），会切换第 $(i \bmod m)$ 盏灯和第 $(2 \times i \bmod m)$ 盏灯的状态。
• 如果这两个编号相同（即 $i \bmod m = 2 \times i \bmod m$），则只切换这一盏灯的状态；
• 切换指：如果灯是关闭的则打开，如果是打开的则关闭。

初始时，所有灯都处于关闭状态。你可以按任意次开关，每个开关可以被多次按下（也可以不按）。

你的目标是让所有灯最终都变为打开的状态。现在，请你计算：最少需要按多少次开关才能做到这一点；如果无论如何操作都无法让所有灯同时打开，则输出 $-1$。

输入格式

第一行包含一个整数 $t$，表示测试数据组数。

接下来 $t$ 组数据，每组数据占一行，包含两个整数 $n$ 和 $m$，分别表示开关的数量和灯的数量。

输出格式

对于每组数据，输出一行，包含一个整数，表示最少需要按开关的次数。如果无法让所有灯都打开，输出 $-1$。

2
4 4
5 5

3
3

提示

【样例说明】

第一组数据：有 $4$ 个开关（编号 $0$ - $3$）和 $4$ 盏灯（编号 $0$ - $3$）。

开关控制关系：

• 开关 $0$：控制灯 $0$（同一盏）；
• 开关 $1$：控制灯 $1$ 和灯 $2$；
• 开关 $2$：控制灯 $2$ 和灯 $0$；
• 开关 $3$：控制灯 $3$ 和灯 $2$.

一种最优方案：按开关 $1$、开关 $2$、开关 $3$，共按 $3$ 次。状态变化如下（关 $= 0$，开 $= 1$）：

第二组数据：有 $5$ 个开关（编号 $0$ - $4$）和 $5$ 盏灯（编号 $0$ - $4$）。

开关控制关系：

• 开关 $0$：控制灯 $0$（同一盏）；
• 开关 $1$：控制灯 $1$ 和灯 $2$；
• 开关 $2$：控制灯 $2$ 和灯 $4$；
• 开关 $3$：控制灯 $3$ 和灯 $1$；
• 开关 $4$：控制灯 $4$ 和灯 $3$。

一种最优方案：按开关 $0$、开关 $1$、开关 $4$，共按 $3$ 次。状态变化如下：

【评测用例规模与约定】

对于 $20\%$ 的数据：$1 \leq t \leq 3$，$1 \leq n, m \leq 8$；

对于 $50\%$ 的数据：$1 \leq t \leq 3$，$1 \leq n, m \leq 20$；

对于 $80\%$ 的数据：$1 \leq t \leq 5$，$1 \leq n, m \leq 100$；

对于 $100\%$ 的数据：$1 \leq t \leq 5$，$1 \leq n, m \leq 1000$。