IAPCR2E - Ballons Revisited

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

Added by:imranziad
Date:2016-06-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Intra AIUB Programming Contest (Mokaddesh Rashid Shovon)

hide comments
2016-10-29 15:15:22
From 40 lines WA to 4 Line AC. ^_^
2016-10-27 00:54:50
Yes! Got AC after 4 was s
2016-07-27 00:11:01
@shadowfax can you please check my submission i m getting correct answer on most of test cases.
2016-06-21 08:38:46 Sushovan Sen
@ test500_spoj
(w=2,r=2,g=1,b=3)=1
then
(w=1,r,1,g=0,b=2)=1 [ You can give four balloons to second child as all of them are not of same colour]
Answer is : 2

Last edit: 2016-06-21 08:41:30
2016-06-12 22:05:23
in frist test case answer should be 1... am i right because...
(w=2,r=2,g=1,b=3)=1
then
(w=1,r,1,g=0,b=2)=0
answer should be 1;
2016-06-10 18:05:51
It is misleading. You need to write labels "Case xxx: " otherwise, you will get a wrong answer :(
2016-06-08 19:11:11
Why does it say "Case 1: " in the example output? Are we supposed to output _only_ the integer answer or not? Very misleading.
2016-06-04 16:00:13 shadowfax
first case: 2w, 2r g, 3b. you can make 2 sets so that each set will contain at least two colors, {w, r, g, b}, and {w, r, b, b}
2016-06-04 00:42:25 KANHAIYA
@imranziad can u explain the sample test case

Last edit: 2016-06-04 00:42:48
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.