题目描述

给定两个均不小于 $2$ 的整数 $N$ 与 $D$。

请在不超过 $N$ 且不是 $D$ 的倍数的正整数中，找出一个正约数个数最多的数。若存在多个这样的正整数，输出其中任意一个均可。

本题有 $T$ 组测试数据，请分别求解。

输入格式

输入按以下格式从标准输入读入：

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

这里，$\text{case}_i$ 表示第 $i$ 组测试数据，其格式如下：

• $N$ $D$

输出格式

输出 $T$ 行。第 $i$ 行应输出第 $i$ 组测试数据的答案。

数据范围

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

4
10 2
17 4
2026 919
1000000000000 48

9
15
1680
843291048600

不超过 $10$ 且不是 $2$ 的倍数的正整数为 $1, 3, 5, 7, 9$ 这五个，它们的正约数个数分别为 $1, 2, 2, 2, 3$。因此第一组测试数据输出 $9$。

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

• 来源：AtCoder ABC 475 G

子任务设置

• 子任务 1（30 分）：$N \le 10^6$。
• 子任务 2（30 分）：$N \le 10^{12}$。
• 子任务 3（40 分）：无特殊限制。