## HS12MULT - Multinomial numbers

You may perhaps know how to find the last nonzero digit of n factorial. This time your task is harder, find the last nonzero decimal digit of the multinomial coefficient:
(a1+a2+ … +an)!/(a1!*a2!* … *an!) . Note that this is an extension of the classical problem, since factorials (and binomial numbers) are also multinomial numbers!

### Input

An integer T, denoting the number of testcases (T≤10000). In each line you are given one positive integer ( n≤20 ), followed by n integers: a1,a2,…,an, where 0 ≤ ai ≤ 1000000000. There are 4 input sets for 10 points.

### Output

Output T lines, the case number followed by the last nonzero decimal digit. See the sample output for the correct format!

### Example

```Input:
7
1 0
2 11 9
4 5 7 2 9
3 1000 3000 2000
3 100000000 200000000 300000000
2 4 9
8 1 1 4 7 4 8 9 2

Output:
Case 1: 1
Case 2: 6
Case 3: 8
Case 4: 6
Case 5: 2
Case 6: 5
Case 7: 4
```

### Warning: A naive algorithm will probably solve only the first two input sets (4 pts).

 Added by: Robert Gerbicz Date: 2012-09-18 Time limit: 1s-1.331s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM32-GCC GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV ICK JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET Resource: High School Programming League 2012/13