IAPCR2E - Ballons Revisited

no tags 

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

hide comments
iharsh234: 2016-10-29 15:15:22

From 40 lines WA to 4 Line AC. ^_^

nonushikhar: 2016-10-27 00:54:50

Yes! Got AC after 4 was s

iharsh234: 2016-07-27 00:11:01

@shadowfax can you please check my submission i m getting correct answer on most of test cases.

Sushovan Sen: 2016-06-21 08:38:46

@ 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
test500_spoj: 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;

filipmaric: 2016-06-10 18:05:51

It is misleading. You need to write labels "Case xxx: " otherwise, you will get a wrong answer :(

ruzihm: 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.

chintz_11: 2016-06-05 10:31:20

Last edit: 2016-06-06 18:09:52
shadowfax: 2016-06-04 16:00:13

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}

KANHAIYA: 2016-06-04 00:42:25

@imranziad can u explain the sample test case

Last edit: 2016-06-04 00:42:48

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)