B. Lunchtime Fruits
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The school canteen has four types of fruits: apricots, bananas, apples, and pears. There are three different possible sets of fruits available for lunch:

  1. two apricots, one banana, and one apple;
  2. two apricots and two apples;
  3. one apricot, one banana, two apples, and one pear.

The canteen's employees want to assemble as many lunch fruit sets for children as possible. Help them do it!

Since the number of fruits delivered is different every day, you need to solve the problem for multiple test cases.

Input

The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The following $$$t$$$ lines contain a description of each test case. Each line contains four integers $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$ ($$$1 \le a, b, c, d \le 10^9$$$) — the number of apricots, bananas, apples, and pears, respectively.

Output

For each test case, print the maximum number of fruit sets it's possible to make.

Scoring
SubtaskScoreConstraints
$$$1$$$$$$10$$$$$$t \le 10$$$; $$$a, b, c, d \le 10$$$
$$$2$$$$$$20$$$$$$t \le 10^4$$$; $$$a, b, c, d \le 10$$$
$$$3$$$$$$20$$$$$$t \le 10$$$; $$$a, b, c, d \le 200$$$
$$$4$$$$$$20$$$$$$t \le 10$$$; $$$a, b, c, d \le 10^6$$$
$$$5$$$$$$30$$$No additional constraints
Example
Input
6
3 3 3 3
3 1 4 1
4 3 2 1
3 3 6 5
9 7 6 7
9 10 10 6
Output
2
2
2
3
5
6
Note

In the first case, you can make two sets of fruits: one of type $$$1$$$ and one of type $$$3$$$.

In the second case, one of the possible answers is $$$(2, 3)$$$.

In the third case, the optimal answer is $$$(1, 1)$$$.

In the fourth case, you can make three sets of type $$$3$$$.