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.


Added by:Robert Gerbicz
Date:2012-09-18
Time limit:1s-1.331s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE
Resource:High School Programming League 2012/13

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