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