Navi is a famous mathematician. He is working on Division, Multiplication and Addition. He is in need of some hidden patterns to discover some new concepts. He is giving you a task to find that sub-sequence of an array which has the maximum P % mod value, where value of the mod is given below. This sub-sequence should have at least 2 elements. P value is defined below:

For some sub-sequence { A_X , A_Y … , A_Z }, P = (A_X * A_Y * … * A_Z) / (A_X + A_Y + … + A_Z)

You have to maximize this P%mod. Take mod as 10⁹ + 7.

Input

First line of the input will have T (no. of test cases). Then for each test case there will be two lines. First line will contain N (no. of integers of array) and the next line will contain N space separated integers.

Output

For each test case print “Case #case_num: ans”. Here ans is maximum P%mod value.

Constraints

1 < = T < = 10
2 < = N < = 16
1 < = A_i < = 10⁷