A - +3 +5 +7 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数 x_1, x_2, x_3 が与えられます．あなたはこれらの整数に対して，次の操作を何度でも行うことができます（0 回でもよい）：

  • (1,2,3) の順列 (i,j,k) をひとつ選ぶ．つまり 1\leq i,j,k\leq 3 であるような整数の組 (i,j,k) であって i\neq j, i\neq k, j\neq k となるものを選ぶ．
  • その後，x_i を x_i+3，x_j を x_j+5，x_k を x_k+7 で同時に置き換える．

あなたの目的は，x_1=x_2=x_3 が成り立つようにすることです．このことが可能であるか否かを判定してください．可能な場合には，それを達成するための最小の操作回数を出力してください．

T 個のテストケースが与えられるので，それぞれについて答えを求めてください．

制約

  • 1\leq T\leq 2\times 10^5
  • 1\leq x_1, x_2, x_3 \leq 10^9

入力

入力は以下の形式で標準入力から与えられます．

T
\text{case}_1
\vdots
\text{case}_T

各テストケースは以下の形式で与えられます．

x_1 x_2 x_3

出力

T 行出力してください．i 行目には i 番目のテストケースについて，次の値を出力してください．

  • x_1=x_2=x_3 が成り立つようにすることが可能ならば，それを達成するための最小の操作回数．
  • x_1=x_2=x_3 が成り立つようにすることが不可能ならば，-1．

入力例 1

4
2 8 8
1 1 1
5 5 10
10 100 1000

出力例 1

2
0
-1
315

ひとつめのテストケースについて，次のように操作を行うことで x_1=x_2=x_3 が成り立つようにできます．

  • (i,j,k) = (3,2,1) として操作を行う．(x_1,x_2,x_3) は (9,13,11) に置き換わる．
  • (i,j,k) = (2,3,1) として操作を行う．(x_1,x_2,x_3) は (16,16,16) に置き換わる．

Score : 300 points

Problem Statement

You are given integers x_1, x_2, and x_3. For these integers, you can perform the following operation any number of times, possibly zero.

  • Choose a permutation (i,j,k) of (1,2,3), that is, a triple of integers (i,j,k) such that 1\leq i,j,k\leq 3 and i\neq j, i\neq k, j\neq k.
  • Then, simultaneously replace x_i with x_i+3, x_j with x_j+5, and x_k with x_k+7.

Your objective is to satisfy x_1=x_2=x_3. Determine whether it is achievable. If it is, print the minimum number of times you need to perform the operation to achieve it.

You have T test cases to solve.

Constraints

  • 1\leq T\leq 2\times 10^5
  • 1\leq x_1, x_2, x_3 \leq 10^9

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each test case is in the following format:

x_1 x_2 x_3

Output

Print T lines. The i-th line should contain the following value for the i-th test case.

  • The minimum number of times you need to perform the operation to satisfy x_1=x_2=x_3, if it is possible to satisfy this.
  • -1, otherwise.

Sample Input 1

4
2 8 8
1 1 1
5 5 10
10 100 1000

Sample Output 1

2
0
-1
315

For the first test case, you can do the following to satisfy x_1=x_2=x_3.

  • Perform the operation with (i,j,k) = (3,2,1), replacing (x_1,x_2,x_3) with (9,13,11).
  • Perform the operation with (i,j,k) = (2,3,1), replacing (x_1,x_2,x_3) with (16,16,16).