Chef and GCD solution codechef

Chef and GCD solution codechef

Chef has two positive integers XX and YY. Now Chef wants to perform some number of operations (possibly zero) on them. In each operation, Chef can choose either XX or YY and increment it by 11. Find the minimum number of operations Chef needs to perform so that there is a positive integer strictly greater than 11 which divides both XX and YY (In other words, the greatest common divisor of XX and YY should be greater than 11).

Input Format

  • The first line contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains two integers XX and YY.

Output Format

For each test case, print a single line containing one integer — the minimum number of operations Chef needs to perform.


  • 1T1051≤T≤105
  • 1X,Y1091≤X,Y≤109

Sample Input 1 

4 16
4 55

Sample Output 1 



Test Case 1: The greatest common divisor of 44 and 1616 is 44 which is already greater than 11, so Chef will not perform any operations.

Test Case 2: Chef will perform one operation and add 11 to 5555. Now the greatest common divisor of 44 and 5656 is 44 which is greater than 11.

Leave a Comment