Migrated from Lutece 1498 E

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

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$ ($1\le T\le 30$), which indicates the number of test cases.

Every test case contains one line with nine integers $a_1,a_2,\ldots,a_9$ ($0\le a_i\le 100$), the $i$-th integer indicates the number of bricks of $i$.

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.

Samples

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

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

Resources

第二届中国大学生程序设计竞赛 杭州站（CCPC 2016 Hangzhou Site）