Problem Statement

You are given integers $N$ and $D$, each at least $2$.

Among the positive integers at most $N$ that are not multiples of $D$, find one with the maximum number of positive divisors. If there are multiple such positive integers, output any one of them.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \leq T \leq 10$
• $2 \leq D \leq N \leq 10^{18}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $T$
• $\text{case}_1$
• $\text{case}_2$
• $\vdots$
• $\text{case}_T$

Here, $\text{case}_i$ represents the $i$-th test case, and is given in the following format:

• $N$ $D$

Output

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

4
10 2
17 4
2026 919
1000000000000 48

9
15
1680
843291048600

The positive integers at most $10$ that are not multiples of $2$ are the five integers $1, 3, 5, 7, 9$, and the numbers of their positive divisors are $1, 2, 2, 2, 3$, respectively. Therefore, output $9$ for the first test case.

For the second test case, besides $15$ in the sample output, outputting any of $6, 10, 14$ is also accepted.

• Source: AtCoder ABC 475 G