Problem Description

You are trapped in an escape room. In front of you is a control panel with $n$ switches that control $m$ lights in the room. The switches are numbered $0, 1, \dots, n - 1$, and the lights are numbered $0, 1, \dots, m - 1$.

The rules for how switches affect lights are as follows:

• Pressing switch $i$ ($0 \leq i < n$) toggles light $(i \bmod m)$ and light $(2 \times i \bmod m)$.
• If these two indices are the same (that is, $i \bmod m = 2 \times i \bmod m$), then only this one light is toggled.
• Toggling means: if a light is off, it becomes on; if it is on, it becomes off.

Initially, all lights are off. You may press switches any number of times. Each switch may be pressed multiple times (or not pressed at all).

Your goal is to make all lights end up on. Now, compute the minimum number of switch presses needed to achieve this. If it is impossible to make all lights on at the same time no matter what you do, output $-1$.

Input Format

The first line contains an integer $t$, the number of testdata groups.

Next come $t$ groups of testdata. Each group consists of one line containing two integers $n$ and $m$, representing the number of switches and the number of lights.

Output Format

For each group of testdata, output one line containing an integer, the minimum number of switch presses. If it is impossible to turn on all lights, output $-1$.

2
4 4
5 5

3
3

Hint

Sample Explanation

In the first group of testdata, there are $4$ switches (numbered $0$ - $3$) and $4$ lights (numbered $0$ - $3$).

Switch-to-light relationships:

• Switch $0$: controls light $0$ (the same light).
• Switch $1$: controls lights $1$ and $2$.
• Switch $2$: controls lights $2$ and $0$.
• Switch $3$: controls lights $3$ and $2$.

One optimal plan is to press switch $1$, switch $2$, and switch $3$, for a total of $3$ presses. The state changes are as follows (off $= 0$, on $= 1$):

In the second group of testdata, there are $5$ switches (numbered $0$ - $4$) and $5$ lights (numbered $0$ - $4$).

Switch-to-light relationships:

• Switch $0$: controls light $0$ (the same light).
• Switch $1$: controls lights $1$ and $2$.
• Switch $2$: controls lights $2$ and $4$.
• Switch $3$: controls lights $3$ and $1$.
• Switch $4$: controls lights $4$ and $3$.

One optimal plan is to press switch $0$, switch $1$, and switch $4$, for a total of $3$ presses. The state changes are as follows:

Constraints

For $20\%$ of the data: $1 \leq t \leq 3$, $1 \leq n, m \leq 8$.

For $50\%$ of the data: $1 \leq t \leq 3$, $1 \leq n, m \leq 20$.

For $80\%$ of the data: $1 \leq t \leq 5$, $1 \leq n, m \leq 100$.

For $100\%$ of the data: $1 \leq t \leq 5$, $1 \leq n, m \leq 1000$.

Translated by ChatGPT 5