/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
非負整数の 3 つ組 (x,y,z) に対する操作を考えます．操作では，(x,y,z) を次の規則に従って置き換えます．
- y+z<x のとき：(x-y-z,\ 2y,\ 2z) に置き換える．
- x+z<y のとき：(2x,\ y-x-z,\ 2z) に置き換える．
- x+y<z のとき：(2x,\ 2y,\ z-x-y) に置き換える．
- 上のいずれの条件も満たさないとき：(y+z-x,\ x+z-y,\ x+y-z) に置き換える．
なおすべての非負整数の 3 つ組は，上記の 4 つの場合のうちちょうど 1 つに該当します．
非負整数 A_1, A_2, A_3, B_1, B_2, B_3 が与えられます．3 つ組 (A_1,A_2,A_3) に対して操作を 0 回以上繰り返し行って，(B_1,B_2,B_3) にすることを考えます．そのために行う操作回数の最小値を求めてください．ただし，何回操作を繰り返しても (B_1,B_2,B_3) にできない場合は，-1 を出力してください．
T 個のテストケースが与えられるので，それぞれについて解いてください．
制約
- 1\leq T\leq 300
- 0\leq A_1, A_2, A_3, B_1, B_2, B_3\leq 10^8
- 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられます．
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられます．
A_1 A_2 A_3 B_1 B_2 B_3
出力
テストケースごとに 1 行出力してください．
各テストケースに対して，3 つ組 (A_1,A_2,A_3) に対して操作を 0 回以上繰り返し行って，(B_1,B_2,B_3) にするために行う操作回数の最小値を出力してください．ただし，何回操作を繰り返しても (B_1,B_2,B_3) にできない場合は，-1 を出力してください．
入力例 1
6 2 3 4 2 3 4 2 3 4 5 3 1 2 3 4 1 6 2 2 3 4 4 3 2 1 0 0 0 0 1 0 0 0 0 0 0
出力例 1
0 1 2 -1 -1 0
(A_1,A_2,A_3)=(2,3,4) である場合，操作を繰り返すと 3 つ組は次のように変化します．
- (2,3,4)\to (5,3,1)\to (1,6,2)\to (2,3,4)\to (5,3,1)\to (1,6,2)\to\cdots
このことから，はじめの 3 つのテストケースの答えが 0, 1, 2 であることが分かります．
Score : 700 points
Problem Statement
Consider an operation on a triple (x,y,z) of non-negative integers. In the operation, (x,y,z) is replaced according to the following rules:
- If y+z<x: replace with (x-y-z,\ 2y,\ 2z).
- If x+z<y: replace with (2x,\ y-x-z,\ 2z).
- If x+y<z: replace with (2x,\ 2y,\ z-x-y).
- If none of the above conditions hold: replace with (y+z-x,\ x+z-y,\ x+y-z).
Note that every triple of non-negative integers falls into exactly one of the above four cases.
You are given non-negative integers A_1, A_2, A_3, B_1, B_2, B_3. Consider performing the operation on the triple (A_1,A_2,A_3) zero or more times to obtain (B_1,B_2,B_3). Find the minimum number of operations required to do so. If it is impossible to obtain (B_1,B_2,B_3) no matter how many times the operation is performed, output -1.
T test cases are given; solve each of them.
Constraints
- 1\leq T\leq 300
- 0\leq A_1, A_2, A_3, B_1, B_2, B_3\leq 10^8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
A_1 A_2 A_3 B_1 B_2 B_3
Output
Output one line per test case.
For each test case, output the minimum number of operations required to obtain (B_1,B_2,B_3) by performing the operation on the triple (A_1,A_2,A_3) zero or more times. If it is impossible to obtain (B_1,B_2,B_3) no matter how many times the operation is performed, output -1.
Sample Input 1
6 2 3 4 2 3 4 2 3 4 5 3 1 2 3 4 1 6 2 2 3 4 4 3 2 1 0 0 0 0 1 0 0 0 0 0 0
Sample Output 1
0 1 2 -1 -1 0
For (A_1,A_2,A_3)=(2,3,4), the triple changes as follows when the operation is repeatedly applied:
- (2,3,4)\to (5,3,1)\to (1,6,2)\to (2,3,4)\to (5,3,1)\to (1,6,2)\to\cdots
From this, we can see that the answers to the first three test cases are 0, 1, 2.