Submit | All submissions | Best solutions | Back to list |

## 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:

(a_{1}+a_{2}+ … +a_{n})!/(a_{1}!*a_{2}!* … *a_{n}!) . 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: a_{1},a_{2},…,a_{n}, where 0 ≤ a_{i} ≤ 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 2Output: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 |