There is an integer . You are allowed to add to any of its divisors not equal to and . The same operation can be applied to the resulting number and so on. Notice that starting from the number , we can reach any composite number by applying several such operations. For example, the number can be reached starting from using operations: .
You have to solve a more general problem. Find the minimal number of the described operations necessary to transform into .
Each line contains two integers and .
For each test case, print in a separate line the minimal number of operations to transform into . Print if can't be obtained from .