While Ali was learning some number theory, he saw the following question and thought it would be a good challenge for you:
Given two integers $a$ and $n$, find the smallest integer $b$ such that:-
$gcd$ stands for greatest common divisor and $gcd$ of two integers ($c$ and $d$) is the greatest integer that divides both ($c$ and $d$). $gcd(12, 20) = 4$, $gcd(9, 14) = 1$.
$lcm$ stands for least common multiple and $lcm$ of two integers ($c$ and $d$) is the least integer that is a multiple of both ($c$ and $d$). $lcm(7, 5) = 35$, $lcm(6, 9) = 18$.
Note: the priority is to maximize the value $lcm(a,b)/gcd(a,b)$, if there are several such integers $b$ that give the same maximum value of $lcm(a,b)/gcd(a,b)$ print the smallest one.
The input consists of multiple test cases. The first line contains a single integer $t (1 \le t \le 10^4)$ --- the number of test cases.
Each test case consists of a single line with two integers $n$ and $a$ $(2 \le a < n \le 10^{18})$.
For each test case, print only one integer as described in the problem statement
| Input | Output |
|---|---|
3 3 2 10 6 9 5 Copy
|
3 7 9 Copy
|
The answer is maximized when $gcd(a, b) = 1$.
Proof: Let $p$ some prime that divides $a$, let $a' = a/p$ which means $a = p * a'$, if we want to choose $b$ to be a multiple of $p$ then $b = p * b'$. We also know that $lcm(a, b) = a*b/gcd(a,b)$, so when we substiute we get $a*b/(gcd(a,b)^2)$ which is equal to $p * a' * p * b'/(gcd(a,b)^2)$ which is $(p^2) * a' * b'/(gcd(a, b) ^ 2)$. Since $p$ is a common factor between $a$ and $b$ then we can say $gcd(a, b) = p * gcd(a', b')$.
So now the equation becomes $(p^2) * a' * b' /((p^2) * (gcd(a',b')^2))$ which is $a' * b'/(gcd(a',b')^2)$. Thus we get any common factor between $a$ and $b$ is actually useless. So we can say $lcm(a, b')/gcd(a, b')$ >= $lcm(a, b)/gcd(a,b)$ and $b' < b$.
So if there is a common factor between $a$ and be we can actually find a smaller answer for $b$ that gives at least the same value of $lcm(a,b)/gcd(a,b)$. Hence we find that $gcd(a,b) = 1$, and now the value becomes $a*b$ so we need to find the maximum $b <= n$ where $gcd(a, b) = 1$. This can be done doing a brute force starting $b$ from $n$ and going down till $gcd(a,b)$ becomes $1$. It won't take us lots of time before we find $b$.