Kelian is a playful girl.
With summer vacation approaching, Kelian plans to build a castle next to her private beach so she can invite her friends over to play during the break. At the same time, Kelian plans to build a maze under the castle, as exploration is always full of fun.
After a simple design, Kelian plans to build a maze as follows: The maze can be abstracted as a directed graph with $n$ nodes and $nm$ edges. Node 1 is the unique entrance and the unique exit. Each node has exactly $m$ outgoing edges, and these edges are labeled with integers from $[0, m)$. * The maze allows self-loops and multiple edges.
At the same time, an excellent maze should have some puzzle-solving elements. Therefore, Kelian hopes that every path starting from node 1 and returning to node 1 follows a certain rule.
Kelian discovered that if you record the labels of all edges along a path starting from 1, you can obtain an $m$-ary number (which may have leading zeros); conversely, every $m$-ary number (which may have leading zeros) corresponds to a path starting from 1.
Thus, Kelian chose an integer $K$, and she hopes that the maze satisfies the condition that a path starting from 1 returns to 1 if and only if the number corresponding to this path is a multiple of $K$.
Now Kelian has already chosen $m$ and $K$, but she finds that not for all $n$ does there exist a maze design that satisfies all the above conditions. Building a maze is a time-consuming and laborious task, so Kelian wants to find the minimum $n$ that satisfies the conditions. However, Kelian is not interested in complex calculations, so she wants you to help her calculate this value.
Input
The first line contains an integer $T$ representing the number of test cases.
Following this, $T$ lines each contain two decimal positive integers $m$ and $K$, representing the integers chosen by Kelian.
Output
For each test case, output a single integer representing the minimum $n$ that satisfies all conditions. If no such $n$ exists, output $-1$.
Examples
Input 1
3 2 3 2 4 6 8
Output 1
3 3 5
Note
One design scheme for the first test case (left) and the second test case (right) is shown in the figure below. The purple edges represent edge 0, and the blue edges represent edge 1.
Constraints
| Test Case | $m$ | $K$ | $t$ | Other |
|---|---|---|---|---|
| 1 | $\le 6$ | $\le 10$ | ||
| 2 | $\le 100$ | None | ||
| 3 | $\le 100$ | $\le 100$ | ||
| 4 | ||||
| 5 | $\le 10^5$ | $\le 10^5$ | ||
| 6 | $m$ is prime | |||
| 7 | $\le 10^9$ | $\le 10^9$ | $\le 1000$ | |
| 8 | None | |||
| 9 | $\le 10^{18}$ | $\le 10^{18}$ | $\le 3 \times 10^5$ | |
| 10 |
For 100% of the data, it is guaranteed that $m \ge 2$.