AT_abc475_g [ABC475G] 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.

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 $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

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