High School Programming League Problems Archive

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₁+a₂+ … +a_n)!/(a₁!*a₂!* … *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₁,a₂,…,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 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.