You have a suitcase with length , width and height . You also have a very comfortable blanket. It has length , width and thickness . You love your blanket very much. You like to take it with you, wherever you go. To fit the blanket in your suitcase, you can apply a fold operation on the blanket.
One fold operation is as follows:
Divide the length or width by .
Multiply the thickness by .
The blanket fits if you can keep it in the suitcase in an axis aligned way. Formally, at least one corner of the blanket must exactly coincide with a corner of the suitcase keeping the entire blanket inside.
Your task is to find the minimum number of fold operations required to fit the blanket in the suitcase. Or report if it is impossible.
Note that it is not necessary to keep the suitcase in input orientation of * * , as long as the orientation is axis aligned.
The first line contains an integer the number of test cases.
Each of the next lines describe a test case with space separated integers . Each of these integers are greater than and do not exceed .
For each test case print a single integer in a separate line.
Print the minimum number of fold required to fit the blanket. If impossible, print .
Input | Output |
---|---|
4 100 100 100 1600 100 6 100 100 100 1600 100 7 32 1024 2048 4096 16384 1 1000000000 10000 100 98 500000000 9899 | 4 -1 5 0 |
In the first case, you can fold the length times to obtain . |