Contents

• For Solution

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 XthXth stair. He has to climb all the way up to the YthYth 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 XthXth stair to the (X+1)th(X+1)th stair. )
• Climb two stairs only if the final stair falls at a prime number position. ( i.e. go from the XthXth stair to the (X+2)th(X+2)th stair, only if (X+2(X+2) is a prime number)

Help Chef reach the YthYth stair from the XthXth stair in minimum number of steps.

See Explanation for more clarity.See Explanation for more clarity.

Note: The input files are large. The use of Fast I/O is recommended.

Chef and Magical Steps solution codechef

• The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
• The first line of each test case contains XX and YY denoting the starting stair and ending stair respectively.

Output Format

• Output a single integer representing minimum number of steps chef can take to reach from XthXth to YthYth stair.

Chef and Magical Steps solution codechef

• 1T1061≤T≤106
• 1X<Y1071≤X<Y≤107

Sample Input 1

4
2 10
5 12
34 43
57 63


Chef and Magical Steps solution codechef

6
5
6
4


Chef and Magical Steps solution codechef

Test case 11: Chef starts from 2nd2nd, goes to 3rd3rd stair, then to 5th5th stair as 55 or (3+2)(3+2) is prime number. Now, from 5th5th stair, Chef goes to 7th7th stair as 77 or (5+2)(5+2) is a prime number, then Chef goes to 8th8th stair, then to 9th9th stair and finally to 10th10th stair. This approach takes a total of 66 steps which is the minimum possible number of steps Chef can take to reach the 10th10th stair starting from the 2nd2nd stair.

Test case 33: Starting from the 34th34th stair, Chef moves through the stairs as following. 3434 → 3535 → 3737 → 3838 → 3939 → 4141 → 4343.