---
{"category_name":"school","problem_code":"CHFGCD","problem_name":"Chef and GCD","problemComponents":{"constraints":"- $1 \\leq T \\leq 10^5$\n- $1 \\leq X, Y \\leq 10^9$","constraintsState":true,"subtasks":"","subtasksState":false,"inputFormat":"- The first line contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\n- The first and only line of each test case contains two integers $X$ and $Y$.\n","inputFormatState":true,"outputFormat":"For each test case, print a single line containing one integer — the minimum number of operations Chef needs to perform.","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"2\n4 16\n4 55","output":"0\n1","explanation":"**Test Case 1:** The greatest common divisor of $4$ and $16$ is $4$ which is already greater than $1$, so Chef will not perform any operations.\n\n**Test Case 2:** Chef will perform one operation and add $1$ to $55$. Now the greatest common divisor of $4$ and $56$ is $4$ which is greater than $1$.","isDeleted":false}}},"video_editorial_url":"https://youtu.be/Swa5WkD2PCk","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":0.5,"source_sizelimit":50000,"problem_author":"souradeep_adm","problem_tester":"aryanc403","date_added":"12-07-2021","tags":{"0":"cakewalk","1":"cook131","2":"greatest","3":"souradeep_adm","4":"vichitr"},"problem_difficulty_level":"Cakewalk","best_tag":"Greatest Common Divisor","editorial_url":"https://discuss.codechef.com/problems/CHFGCD","time":{"view_start_date":1627492504,"submit_start_date":1627492504,"visible_start_date":1627492504,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=CHFGCD","is_proctored":false,"visitedContests":{},"layout":"problem"}
---
### Read problems statements in [Mandarin Chinese](https://www.codechef.com/download/translated/COOK131/mandarin/CHFGCD.pdf), [Russian](https://www.codechef.com/download/translated/COOK131/russian/CHFGCD.pdf), [Vietnamese](https://www.codechef.com/download/translated/COOK131/vietnamese/CHFGCD.pdf) and [Bengali](https://www.codechef.com/download/translated/COOK131/bengali/CHFGCD.pdf) as well.
Chef has two positive integers $X$ and $Y$. Now Chef wants to perform some number of operations (possibly zero) on them. In each operation, Chef can choose either $X$ or $Y$ and increment it by $1$. Find the minimum number of operations Chef needs to perform so that there is a positive integer strictly greater than $1$ which divides both $X$ and $Y$ (In other words, the greatest common divisor of $X$ and $Y$ should be greater than $1$).
<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>