Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Prime Avoider

By MosharrafOshy · Limits 1s, 512 MB

Mr. X is a friend of Hafiz bhai. Mr. X loves to play with numbers in his leisure but he hates prime number. A prime number is which can be only divisible by 1 and itself.

One day to make his leisure enjoyable Hafiz bhai gave him a problem. The problem is that, there are two numbers A and B. Mr. X has to turn the number A into B. This thing looks easy to Mr. X , but little did he know.. Being clever, Hafiz bhai told him to do it with the following conditions in mind:

  1. If A = 22, Mr. X can increase/decrease any digit by 1. So Mr. X can change 22 into 23, 21, 32 or 12. (If any digit is 0 then Mr. X cannot decrease it and if any digit is 9 Mr. X cannot increase it, It means if a digit is 0, Mr. X cannot change it into -1 or 9 and if a digit is 9, Mr. X cannot change it into 10 or 0).

  2. When he changes the number by increasing or decreasing any digit, the new number cannot be a prime number. For example, Mr. X can change 22 into 21, 32 or 12, but not 23.

  3. If A = 22 and B = 34 then a way that Mr. X gets B from A is:

    22 → 32 → 33 → 34

  4. Total cost of this change is (22 + 32 + 33 + 34) = 121 (Summation of numbers that appear in the process of getting B from A) and there can be many more ways.

As Mr. X hates prime numbers (actually afraid of prime numbers), he came to you and asked for help. He knows you are a good programmer. He gave you A and B. You have to find out the minimum cost to get B from A.

Input

Input starts with an integer T (T ≤ 10), denoting the number of test cases. Each case starts with a line contains two integers A and B (1 ≤ A, B ≤ 105). Length of A and B will be equal and there can be leading zeroes.

Output

For each case, print the case number and minimum cost to get B from A. If it is impossible to get B from A then print -1.

Sample

InputOutput
3
22 34
10 12
2 4
Case 1: 121
Case 2: 85
Case 3: -1


Discussion
Statistics

37% Solution Ratio

dip_BRUREarliest, Nov '17

IshrakFastest, 206734.6s

IshrakLightest, 7.5 MB

dip_BRURShortest, 2796B

Submit

Login to submit