Server Time: Wed Sep 23, 2020 6:44 am
Welcome ( logout
E - Number Transformation
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

In this problem, you are given an integer number s. You can transform any integer number A to another integer number B by adding x to A. This x is an integer number which is a prime factor of A (please note that 1 and A are not being considered as a factor of A). Now, your task is to find the minimum number of transformations required to transform s to another integer number t.

Input

Input starts with an integer T (≤ 500), denoting the number of test cases.

Each case contains two integers: s (1 ≤ s ≤ 100) and t (1 ≤ t ≤ 1000).

Output

For each case, print the case number and the minimum number of transformations needed. If it's impossible, then print -1.

Sample Input

Output for Sample Input

2

6 12

6 13

Case 1: 2

Case 2: -1

 


Problem Setter: Mohammad Mahmudur Rahman
Special Thanks: Jane Alam Jan (Solution, Dataset)
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan