Chef and GCD solution codechef
Chef has two positive integersand . Now Chef wants to perform some number of operations (possibly zero) on them. In each operation, Chef can choose either or and increment it by . Find the minimum number of operations Chef needs to perform so that there is a positive integer strictly greater than which divides both and (In other words, the greatest common divisor of and should be greater than ).
- The first line contains a single integer denoting the number of test cases. The description of test cases follows.
- The first and only line of each test case contains two integers and .
For each test case, print a single line containing one integer — the minimum number of operations Chef needs to perform.
Sample Input 1
2 4 16 4 55
Sample Output 1
Test Case 1: The greatest common divisor ofand is which is already greater than , so Chef will not perform any operations.
Test Case 2: Chef will perform one operation and addto . Now the greatest common divisor of and is which is greater than .