Trong một buổi học của một lớp học nọ, cô giáo chủ nhiệm muốn tổ chức hoạt động "cặp đôi cùng tiến" nhằm nâng cao tình bạn cũng như cải thiện thành tích học tập của các bạn. Theo đó, cô giáo sẽ chia các bạn thành cặp sao cho mỗi bạn trong lớp được ghép với chính xác một bạn khác. Qua khảo sát về sở thích ghép cặp của các bạn, cô giáo biết được trong lớp có:

• ~a~ bạn nam muốn được ghép cặp với một bạn nam khác;

• ~b~ bạn nam muốn được ghép cặp với một bạn nữ;

• ~c~ bạn nữ muốn được ghép cặp với một bạn nữ khác và;

• ~d~ bạn nữ muốn được ghép cặp với một bạn nam.

Để những "đôi bạn cùng tiến" được hiệu quả, cô giáo sẽ ghép cặp sao cho số bạn được ghép cặp theo ý muốn là lớn nhất. Các bạn hãy giúp cô giáo nhé.

Input

Dòng đầu tiên chứa số nguyên ~t~ ~(1 \le t \le 20)~ là số bộ dữ liệu. Tiếp theo là ~t~ dòng, mỗi dòng gồm bốn số nguyên ~a, b, c, d~ ~(1 \le a, b, b, d \le 5 \cdot 10^8)~ mô tả một bộ dữ liệu. Dữ liệu đảm bảo tổng số học sinh trong lớp, tức ~a+b+c+d~ là một số chẵn.

Output

Với mỗi bộ dữ liệu, in ra một số nguyên là số bạn tối đa được ghép cặp theo ý muốn. Các số được viết trên một dòng, cách nhau bởi dấu cách.

Scoring

Sample Input 1

2
1 1 1 1
2 1 2 1

Sample Output 1

2 6