Limits 1s, 512 MB

You have a suitcase with length XX, width YY and height ZZ. You also have a very comfortable blanket. It has length LL, width WWand thickness HH. 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 22.

  • Multiply the thickness by 22.

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 XX * YY * ZZ, as long as the orientation is axis aligned.


The first line contains an integer T(1T105)T( 1 \leq T \leq 10^5) the number of test cases.
Each of the next TT lines describe a test case with 66 space separated integers X,Y,Z,L,W,HX, Y, Z, L, W, H. Each of these 66 integers are greater than 00 and do not exceed 10910^9.


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


100 100 100 1600 100 6
100 100 100 1600 100 7
32 1024 2048 4096 16384 1
1000000000 10000 100 98 500000000 9899

In the first case, you can fold the length 44 times to obtain (L,W,H)=(100,100,96)(L, W, H) = (100, 100, 96).
In the second case, no sequence of operation can make it possible.
In the third case, after fold-ing the length and width 11 time and 44 times respectively, you can obtain (L,W,H)=(2048,1024,32)(L, W, H) = (2048, 1024, 32). Which fits the suitcase exactly. A suitcase (32,1024,2048)(32, 1024, 2048)can be oriented in an axis aligned way to (2048,1024,32)(2048, 1024, 32).
In the fourth case, it already fits. So no operation is necessary.


Login to submit.


57% Solution Ratio
rifatrraazzEarliest, Feb '23
Xiao_NaiFastest, 0.1s
Kuddus.6068Lightest, 4.9 MB
mdshadeshShortest, 777B
Toph uses cookies. By continuing you agree to our Cookie Policy.