---{"category_name":"easy","problem_code":"CHEFMGX","problem_name":"Chef and Magical Steps","problemComponents":{"constraints":"- $1 \\leq T \\leq 10^6$\n- $1 \\leq X \\lt Y \\leq 10^7$\n","constraintsState":true,"subtasks":"","subtasksState":false,"inputFormat":"- The first line contains an integer $T$ denoting the number of test cases. The $T$ test cases then follow.\n- The first line of each test case contains $X$ and $Y$ denoting the starting stair and ending stair respectively.","inputFormatState":true,"outputFormat":"- Output a single integer representing minimum number of steps chef can take to reach from $X^{th}$ to $Y^{th}$ stair.","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"4\n2 10\n5 12\n34 43\n57 63","output":"6\n5\n6\n4","explanation":"**Test case $1$**: Chef starts from $2^{nd}$, goes to $3^{rd}$ stair, then to $5^{th}$ stair as $5$ or $(3+2)$ is prime number. Now, from $5^{th}$ stair, Chef goes to $7^{th}$ stair as $7$ or $(5+2)$ is a prime number, then Chef goes to $8^{th}$ stair, then to $9^{th}$ stair and finally to $10^{th}$ stair. This approach takes a total of $6$ steps which is the minimum possible number of steps Chef can take to reach the $10^{th}$ stair starting from the $2^{nd}$ stair. \n\n**Test case $3$**: Starting from the $34^{th}$ stair, Chef moves through the stairs as following. $34$ \u0026#x2192; $35$ \u0026#x2192; $37$ \u0026#x2192; $38$ \u0026#x2192; $39$ \u0026#x2192; $41$ \u0026#x2192; $43$.","isDeleted":false}}},"video_editorial_url":"","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":2,"source_sizelimit":50000,"problem_author":"shivyyy_21","problem_tester":"mexomerf","date_added":"24-09-2021","tags":{"0":"easy","1":"shivyyy_21","2":"sieve","3":"start16"},"problem_difficulty_level":"Easy","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/CHEFMGX","time":{"view_start_date":1634751002,"submit_start_date":1634751002,"visible_start_date":1634751002,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=CHEFMGX","is_proctored":false,"visitedContests":{},"layout":"problem"}---Chef has a new customer and he wants to prepare his order as soon as possible. While preparing, he sees that the mint sauce is finished. He has to run upstairs to get it from other kitchen. Chef is currently on the $X^{th}$ stair. He has to climb all the way up to the $Y^{th}$ stair in minimum number of steps. In one step, Chef can do one of the following things:- Climb a single stair. ( i.e go from the $X^{th}$ stair to the $(X+1)^{th}$ stair. )- Climb two stairs only if the final stair falls at a prime number position. ( i.e. go from the $X^{th}$ stair to the $(X+2)^{th}$ stair, only if $(X + 2$) is a prime number)Help Chef reach the $Y^{th}$ stair from the $X^{th}$ stair in minimum number of steps.$\textbf{See Explanation for more clarity.}$**Note:** The input files are large. The use of Fast I/O is recommended.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>