SOLVE

LATER

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

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.
**

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...