AT_abc475_g [ABC475G] Has Many Divisors

$ 2 $ 以上の整数 $ N, D $ が与えられます。 $ N $ 以下の正整数であって $ D $ の倍数でないもののうち、正の約数の個数が最も多いものを求めてください。ただし、そのような正整数が複数存在する場合には、いずれか $ 1 $ つを出力してください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ ここで、 $ \text{case}_i $ は $ i $ 番目のテストケースであり、以下の形式で与えられる。 > $ N $ $ D $

$ T $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 10 $ 以下の正整数であって $ 2 $ の倍数でないものは $ 1, 3, 5, 7, 9 $ の $ 5 $ つであり、それぞれ正の約数の個数は $ 1, 2, 2, 2, 3 $ です。したがって、 $ 1 $ 番目のテストケースでは $ 9 $ を出力します。 $ 2 $ 番目のテストケースでは、出力例の $ 15 $ のほか、 $ 6, 10, 14 $ のいずれかを出力しても正答となります。 ### Constraints - $ 1 \leq T \leq 10 $ - $ 2 \leq D \leq N \leq 10^{18} $ - 入力される値はすべて整数