Equation

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Description

Little Ruins is a studious boy, recently he learned addition operation! He was rewarded some number bricks of $1$ to $9$ and infinity bricks of addition mark '+' and equal mark '='.

Now little Ruins is puzzled by those bricks because he wants to put those bricks into as many different addition equations form $x + y = z$ as possible. Each brick can be used at most once and x, y, z are one digit integer.

As Ruins is a beginer of addition operation, $x$, $y$ and $z$ will be single digit number.

Two addition equations are different if any number of $x$, $y$ and $z$ is different.

Please help little Ruins to calculate the maximum number of different addition equations.

Input

First line contains an integer $T$, which indicates the number of test cases.

Every test case contains one line with nine integers, the $i^{th}$ integer indicates the number of bricks of $i$.

Limits
$1 \leq T \leq 30$
$0 \leq \text{bricks number of each type} \leq 100$

Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.

Sample Input

3 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 0 3 3 0 3 0 0 0 0

Sample Output

Case #1: 2 Case #2: 6 Case #3: 2

Hint

liuyiding

Source

2016年中国大学生程序设计竞赛(杭州)

提交代码