Time Limit: 1.0 s

Memory Limit: 512.0 MB

Description

The last few days remain before the FIFA world cup 2022. Mr. Cloud is in a big rush to complete his assigned task. The work was going at full speed. But here the problem arises. The construction work suddenly stopped due to the shortage of bricks. Alas! Mr. Cloud has fallen into deep thought about how to complete the rest of the work as he knows that he was given the complete allocation of the work. But due to some miscalculation, he felt short!

You being a good friend of Mr. Cloud, come to know about this problem and decided to help him. You’ve visited the area and found out that there are some broken bricks and you can merge them to make 3∗3 shape bricks(because in SchrodenBug the bricks are of 3∗3 square shape). The shapes of broken bricks are 1∗1,1∗2,1∗3, and the L shape which is a 1∗1 shape above 1∗2 shape(Check the image below for clear visualization). You can rotate the shapes 90° clockwise or anticlockwise.

Mr. Cloud became so happy hearing that you found a solution for him, then he asked you how many bricks can you make by merging them.

You know how many broken of all these shapes are available. Help Mr. Cloud find the maximum possible bricks possible to assemble.

Format

Input

Given t(1 <= t <= 10), the number of test cases. Each test case is followed by four integers a,b,c,d

• a - number of broken bricks of 1∗1 shape
• b - number of broken bricks of 1∗2 shape
• c - number of broken bricks of 1∗3 shape
• d - number of broken bricks of the L shape

Constraint
0<=a,b,c,d<=40

Output

For each test case, print the case number followed by the answer to the query of the problem. See the sample 1 explanation for better understanding.

Sample 1

Input

2
1 1 3 1
0 0 3 0

Output

Case 1: 1
Case 2: 1

Sample 2

Input

1
4 16 0 0

Output

Case 1: 4

Explanation

In the first test case of sample 1, you can take one broken brick of all shapes and make a complete brick as follow.

In the second test case of sample 1, you can take three 1∗3 block and assemble one brick.