You have w white, r red, g green and b blue balloons. To make a single student happy you need exactly four balloons. All four balloons given to a student shouldn't have the same color. What is the maximum number S of happy students if we know number of balloons of each color?

Your task is to write a program that for given values w,r, g and b will find the S.

Input

Input starts with an integer T (≤ 20000), denoting the number of test cases.

Each test case contains four integers w,r, g and b (0 ≤ w,r, g, b ≤ 10^9) — the number of white,red, green and blue balloons respectively. The numbers are separated by exactly one space.

Output

For each test case print a single integer S — maximum number of happy students.

Example

Input:
2
2 2 1 3
1 1 4 1
Output:
Case 1: 2
Case 2: 1