Lcm hates Gcd solution codechef

Lcm hates Gcd solution codechef – Chef has two integers  and .
Chef wants to find the minimum value of lcm(�,�)−gcd(�,�) where  is any positive integer.

Lcm hates Gcd solution codechef

Help him determine this value.

Note: gcd(�,�) denotes the greatest common divisor of  and  and lcm(�,�) denotes the least common multiple of  and .

Input Format

  • The first line contains a single integer  — the number of test cases. Then the test cases follow.
  • The first and only line of each test case contains two space-separated integers  and  — the integers mentioned in the statement.

Output Format

For each test case, output the minimum value of lcm(�,�)−gcd(�,�).

Lcm hates Gcd solution codechef

  • 1≤�≤105
  • 1≤�,�≤109

Sample 1:

Input

Output

3
12 15
5 50
9 11
9
0
8

Lcm hates Gcd solution codechef Explanation:

Test case 1: For �=6lcm(12,6)−gcd(15,6)=12−3=9 which is the minimum value required.

Test case 2: For �=50lcm(5,50)−gcd(50,50)=50−50=0 which is the minimum value required.

Test case 3: For �=1lcm(9,1)−gcd(11,1)=9−1=8 which is the minimum value required.

Leave a Reply

Your email address will not be published. Required fields are marked *