Two numbers ~a~ and ~b~ are considered coprime if they do not have any common prime factors. For example, ~4~ and ~9~ are coprime, while ~4~ and ~6~ are not.

Given ~a~ and ~K~, can you find the largest value of ~b~ such that ~a~ and ~b~ are coprime, and ~1 < b \le K~? You will be given ~T~ of these cases.

Input Specification

The first line will contain the integer ~T~ ~(T \in \{1,100\})~, the number of cases. There will either be ~1~ case or ~100~ cases.

The next ~T~ lines will contain two integers, ~a, K~ ~(2 \le a, K \le 10^{16})~. Note that these integers will not fit in a 32-bit data type (e.g. int). Please use a 64-bit data type (e.g. long).

Output Specification

For each case, output the value of ~b~ described in the problem statement on its own line. It is guaranteed the value exists.

Sample Input 1

1
14 28

Sample Output 1

27

Sample Input 2

1
30030 126

Sample Output 2

113