Description

Summer vacation is coming, and Kelian plans to build a castle next to her private beach so she can invite her friends over during the holidays. She also plans to build a maze under the castle, because exploration is always fun.

After a simple design, Kelian plans to build a maze as follows:

• The maze can be abstracted as a directed graph with $n$ vertices and $nm$ edges. Vertex $1$ is the only entrance and also the only exit.
• Each vertex has exactly $m$ outgoing edges, and these outgoing edges are labeled in order by integers in $[0, m)$.
• Self-loops and parallel edges are allowed.

A good maze should also have some puzzle elements. Kelian hopes that every cycle starting from vertex $1$ and returning to vertex $1$ follows a certain pattern. She finds that if you record the labels of all edges along a path starting from vertex $1$, you obtain a base-$m$ number (possibly with leading $0$s). Conversely, for every base-$m$ number (possibly with leading $0$s), there exists a corresponding path starting from vertex $1$.

Kelian then chooses an integer $K$. She wants the maze to satisfy: a path starting from vertex $1$ returns to vertex $1$ if and only if the number corresponding to this path is a multiple of $K$.

Now that $m$ and $K$ have been chosen, she realizes that not every $n$ admits a maze design that meets all the conditions above. Since building a maze is time-consuming and laborious, Kelian wants to find the minimum $n$ that satisfies the conditions.

However, Kelian is not interested in complicated calculations, so she asks you to compute this value for her.

Input Format

The first line contains an integer $T$ — the number of test cases.

Each of the next $T$ lines contains two positive decimal integers $m, K$ — the chosen integers.

Output Format

For each test case, output a single integer: the minimum $n$ that satisfies all the conditions. If no such $n$ exists, output -1.

3 
2 3
2 4 
6 8

3 
3
5

Hint

One possible design for the first test case (left) and the second test case (right) is shown below. Purple edges denote the edge labeled $0$, and blue edges denote the edge labeled $1$.

Translated by ChatGPT 5