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.