final-destination

You’ve just come out of a theatre after watching X-Men, and you’re thinking of mutation. You cannot just move on. You’re stuck on mutation, and its issues. But unlike mutants in the movie, you’re just another Mathematician, with the four basic powers:  
Addition
Subtraction
Division
Multiplication

And with every power there’s associated a number. And you are allowed to use only the number associated with a power, when using that power. After deciding all those rules, and powers, you feel better about yourself and decide to take on the task of converting one number to another, using your powers. But, here’s the tricky part -   

NOTE:
All calculations done using your powers should be done in a way so that they never exceed 1000000 and should  never go below 2 as well.

You’ve to output the minimum number of  minimum number of   steps to reach from a to b using powers.  

input:
First line of input contains T, number of test cases . Each test case contains two lines , first line contains two integers a and b, second line contains four integer that Mul, Div, Add and Sub numbers associated with power of Multiplication, Division, Addition and Subtraction.  

Output:
For each test case print the minimum number of   steps to reach from a to b using powers, if not possible print -1 .  

Constraints:
1 ≤ T ≤ 100
1 ≤ a ≤ b ≤ 10000
1 ≤ Mul ≤ Div ≤ 1000  
0 ≤ Add ≤ Sub ≤ 1000  

SAMPLE INPUT
3
2 4
2 1 1 1
2 4
1 2 3 4
2 5
1 2 3 4

SAMPLE OUTPUT
1
3
1

Explanation

Test Case#1:
Source= 2 and Destination=4
Value of Mul=2, Div=1, Add=1 and Sub=1
You can go from source to destination with one step that is 2*2=4.   

Test Case#2:
Source=2 and Destination =4 
Value of Mul=1, Div=2, Add=3 and Sub=4
Then the possible path will be:
Step1:  2+3 = 5
Step2:  5+3 = 8
Step3:  8/2= 4

Note: You can't use Div operation is first step because *All calculations done using your powers should be done in a way so that they never exceed 1000000 and should never go below 2 as well.
*

Source: hackerearth | Difficulty: EASY
Tags: Graph traversal


Solutions: