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:
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).
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.
If A = 22 and B = 34 then a way that Mr. X gets B from A is:
22 → 32 → 33 → 34
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 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.
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.
| Input | Output |
|---|---|
3 22 34 10 12 2 4 | Case 1: 121 Case 2: 85 Case 3: -1 |