AT_abc475_g.Has Many Divisors

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.

给你两个整数 $N$ 和 $D$，均至少为 $2$。

在不超过 $N$ 的正整数中，找出一个不是 $D$ 的倍数的数，使其正因数个数最多。若存在多个满足条件的数，输出其中任意一个即可。

你将得到 $T$ 组测试数据；请对每组数据分别求解。

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$

输入从标准输入中按以下格式给出：

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

其中，$\text{case}_i$ 表示第 $i$ 个测试用例，其格式如下：

$N$ $D$

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

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

Sample 1 Explanation:
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.

Constraints

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

样例 1 解释：
不超过 $10$ 的正整数中，不是 $2$ 的倍数的数共有五个：$1, 3, 5, 7, 9$；它们各自的正因数个数分别为 $1, 2, 2, 2, 3$。因此，第一个测试用例的输出为 $9$。

对于第二个测试用例，除样例输出中的 $15$ 外，输出 $6, 10, 14$ 中的任意一个也被接受。

约束条件

• $1 \leq T \leq 10$
• $2 \leq D \leq N \leq 10^{18}$
• 所有输入值均为整数。