VIP Hall

Time Limit: 2 Seconds    Memory Limit: 131072 KB

An interior designer is invited to decorate a big VIP hall in one of the greatest software development companies. This company only wants to use rectangular coffee tables with size of 1 × 3 which means that it is appropriate for at most 8 persons as shown in figure 1. This company has bought sofas in three types of 1-person sofa, 2-person sofa and 3-person sofa for its VIP hall and wants to buy coffee tables as many that no sofas remains without a table. The company wants the designer to arrange these sofas in a way that the number of necessary coffee tables minimizes. Since there are a lot of sofas to arrange, the designer asks you to write a program to compute minimum number of coffee tables to be used in the VIP hall given the information of available sofas.

Input

First line of the input contains an integer N which is number of test cases. Each of the following N lines contains three separate integers s ₁, s₂ and s₃ denoting number of 1-person sofas, 2-person sofas and 3-person sofas respectively where 0 <= s₁, s₂, s₃ <= 1000 and s₁ + s₂ + s ₃ >= 1.

Output

For each test, print a single line containing minimum number of coffee tables to buy.

Sample Input

3
9 2 1
10 0 0
2 2 4

Sample Output

2
2
3

Submit