你被困在一个密室中，面前有一个控制面板，上面有 n 个开关，控制着密室中的 m 盏灯。开关编号为 0, 1,. . . , n − 1，灯编号为 0, 1,. . . , m − 1。
开关与灯的作用规则如下：
• 按下第 i 个开关（0 ≤ i < n），会切换第 (i mod m) 盏灯和第 (2 × i mod m)
盏灯的状态。
• 如果这两个编号相同（即 i mod m =2 × i mod 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）：
| 状态 | 控制灯 | 灯0 | 灯1 | 灯2 | 灯3 |
| 初始状态 | 关 | 关 | 关 | 关 | |
| 按开关1 | 灯1，2 | 关 | 开 | 开 | 关 |
| 按开关2 | 灯2，0 | 开 | 开 | 关 | 关 |
| 按开关3 | 灯3，2 | 灯 | 开 | 开 | 开 |
第二组数据：有 5 个开关（编号 0- 4）和 5 盏灯（编号 0- 4）。
开关控制关系：
• 开关 0：控制灯 0（同一盏）；
• 开关 1：控制灯 1 和灯 2；
• 开关 2：控制灯 2 和灯 4；
• 开关 3：控制灯 3 和灯 1；
• 开关 4：控制灯 4 和灯 3。
一种最优方案：按开关 0、开关 1、开关 4，共按 3 次。状态变化如下：
| 状态 | 控制灯 | 灯0 | 灯1 | 灯2 | 灯3 | 灯4 |
| 初始状态 | 关 | 关 | 关 | 关 | 关 | |
| 按开关0 | 灯0 | 开 | 关 | 关 | 关 | 关 |
| 按开关1 | 灯1，2 | 开 | 开 | 开 | 关 | 关 |
| 按开关4 | 灯4，3 | 开 | 开 | 开 | 开 | 开 |
【评测用例规模与约定】
对于 20% 的数据：1 ≤ t ≤ 3，1 ≤ n, m ≤ 8；
对于 50% 的数据：1 ≤ t ≤ 3，1 ≤ n, m ≤ 20；
对于 80% 的数据：1 ≤ t ≤ 5，1 ≤ n, m ≤ 100；
对于 100% 的数据：1 ≤ t ≤ 5，1 ≤ n, m ≤ 1000。