A - Make 10 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

長さが 2 の棒が N_2 個、長さが 3 の棒が N_3 個、長さが 4 の棒が N_4 個あります。あなたは、これらの棒に対して次の操作を何度でも行うことができます：

  • 2 つの棒を選ぶ。
  • 選んだ棒の長さが x, y であるとき、これらを接着することで、長さ x+y の棒を作る。

長さがちょうど 10 に等しい棒を最大でいくつ作れるかを求めてください。

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

制約

  • 1\leq T\leq 100
  • 0\leq N_2, N_3, N_4\leq 10^{15}

入力

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

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

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

N_2 N_3 N_4

出力

T 行出力してください。i 行目には、\text{case}_i に対する答えを出力してください。

入力例 1

5
3 4 1
7 0 0
0 0 7
0 0 0
1000000000000000 1000000000000000 1000000000000000

出力例 1

2
1
0
0
900000000000000

ひとつめのテストケースについて説明します。 長さ 2 の棒が 3 個、長さ 3 の棒が 4 個、長さ 4 の棒が 1 個あります。

例えば以下のようにして、長さがちょうど 10 の棒を 2 個作ることができます。

  • 長さが 2, 2, 3, 3 の棒を適当な順序で接着することで、長さが 10 の棒をひとつ作ることができます。
  • 長さが 3, 3, 4 の棒を適当な順序で接着することで、長さが 10 の棒をひとつ作ることができます。
  • これらの操作の後、長さが 2, 10, 10 の棒が手元に残ります。

Score : 300 points

Problem Statement

We have N_2 sticks of length 2 each, N_3 sticks of length 3 each, and N_4 sticks of length 4 each. You can do the following operation any number of times.

  • Choose two sticks.
  • Let x and y be the lengths of these sticks. Bond them to form a stick of length x+y.

Find the maximum number of sticks that can be made whose lengths are exactly 10.

Given T test cases, solve each of them.

Constraints

  • 1\leq T\leq 100
  • 0\leq N_2, N_3, N_4\leq 10^{15}

Input

Input is given from Standard Input in the following format:

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

Each case is in the following format:

N_2 N_3 N_4

Output

Print T lines; the i-th line should contain the answer for \text{case}_i.

Sample Input 1

5
3 4 1
7 0 0
0 0 7
0 0 0
1000000000000000 1000000000000000 1000000000000000

Sample Output 1

2
1
0
0
900000000000000

Let us describe the first case. We have three sticks of length 2, four sticks of length 3, and one stick of length 4.

One way to make two sticks of length exactly 10 is as follows.

  • Bond four sticks of length 2, 2, 3, 3 in some order to make one stick of length 10.
  • Bond three sticks of length 3, 3, 4 in some order to make one stick of length 10.
  • Now we have three sticks of length 2, 10, 10.