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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.