Dear Solver,

This is your reminder for the new episode airing of Too Many Losing Heuristics!, as per your notification settings on MyAlgorithmList (MAL).

In this new episode, Nukumizu is locked in the gym storage room, alone this time! The room seems infinitely large though, but luckily, he knows where an alternative exit is! There are also some walls that he can't walk into — they occur whenever the coordinates of the space, x y, satisfy x * y + 1 is prime. If this is negative, it will never be considered prime.

Unfortunately, the summer heat is causing him to dehydrate, and so he wants to minimise the number of moves to the exit. He can move to any square directly adjacent to him (no diagonals).

He initially tries navigating by brute-force but doesn't get any closer — his mind is spinning! He tries asking Lemon for help, but she suggests sprinting around while doing BFS — the search area just seems too large! He tries asking Yanami for help, but she just suggests Dijkstra’s — and for some reason he can't compute, it just won't terminate!

He is really tired and dehydrated now so he gives up, stranded somewhere in the room. There are simply too many losing heuristics to navigate by!

Maybe you can tell him the minimum moves to the exit before the next episode airs? His current location and the location of the alternative exit is typed below.

Find the minimum number of moves from where he ended up to the alternative exit.

Input Format:

• The first line contains two integers sx and sy, representing the coordinates of the starting point.
• The second line contains two integers ex and ey, representing the coordinates of the exit location.
These squares are guaranteed to not contain walls.

Output:

• Output a single integer representing the minimum number of moves required to reach the exit.

Sample Input:

11 11
30 30

Sample Output:

44

Sample Explanation:

The shortest path from 11, 11 to 30, 30 consists of 44 moves.