Clues

Dr. Wolf is an employee of Academic Cipher Machinery (ACM). His work is to secure a plenty of electronic documents by using a cipher machine invented by ACM. Given a document, the cipher machine is capable of making it encrypted whenever an arbitrary prime number, called the key prime, is provided. In mathematics, a prime number is a positive integer which has exactly two distinct positive divisors: 1 and itself. Of course, an encrypted document can be decrypted if the corresponding key prime is available. As a consequence, Dr. Wolf picked many key primes for those documents to be secured. This seems to be an easy task. However, Dr. Wolf found that it is very difficult for him to remember so many key primes. Therefore, he decided to write down some information of the key primes in a notebook. To ensure safety, only a clue is recorded for each key prime. Let k0 be a key prime. Dr. Wolf produces a clue C for k0 according to the following strategy. Initially, C is an empty sequence. In Step 1, select an integer r ≥ 1 as well as r − 1 prime numbers k1,k2,...,kr−1 that are not larger than k0, and then include r into C. In Step 2, for each ki, 0 ≤ i ≤ r − 1, either include ki into C, or partition ki into smaller positive integers (adding up to exactly ki) and then include the smaller integers into C. Finally, in Step 3, rearrange the integers in C non-decreasingly. For example, a clue for k0 = 13 is made as follows. In Step 1, select r = 4 and (k1, k2, k3) = (5, 5, 7), and include 4 into C. In Step 2, partition k0 = 13 into (2, 4, 7), partition k1 = 5 into (1, 4), partition k2 = 5 into (2, 3), and partition k3 = 7 into (1, 1, 5). After Step 2, we have C = (4,2,4,7,1,4,2,3,1,1,5). Finally, in Step 3, we obtain a clue C = (1,1,1,2,2,3,4,4,4,5,7). Dr. Wolf would use clues to recover the original key primes. Unfortunately, Dr. Wolf found that there is a drawback in his strategy: the key prime that can be inferred from a given clue may not be unique! For example, consider the clue C = (1,1,1,2,2,3,4,4,4,5,7). We may conclude k0 = 13 by letting r = 4 and (k0,k1,k2,k3) = (2+4+7,1+4,2+3,1+1+5) = (13,5,5,7). However, we may also concludek0 =17bylettingr=4and(k0,k1,k2,k3)=(2+4+7+4,1+2,3,1+1+5)=(17,3,3,7), orconcludek0 =29bylettingr=2and(k0,k1)=(2+3+4+4+4+5+7,1+1+1)=(29,3). To overcome this drawback, Dr. Wolf calls a clue of a key prime k0 good if the largest key prime that can be inferred from it is k0. In the above example, C = (1,1,1,2,2,3,4,4,4,5,7) is good if k0 = 29. In order to produce good clues, Dr. Wolf needs a program that computes the largest key prime that can be inferred from a given clue. Therefore, Dr. Wolf seeks for your help. Technical Specification

Thenumberofintegersinaclue,n: 3≤n≤14. 2. Each integer in a clue ranges from 1 to 10000. Input There are at most 25 test cases. Each test case describes a clue C = (c1, c2, . . . , cn) in two lines. The first line contains the integer n, where 3 ≤ n ≤ 14. The second line contains the n integers c1, c2, . . . , cn, where 1 ≤ c1 ≤ c2 ≤ ··· ≤ cn ≤ 10000. The last test case is followed by a line containing a number ‘-1’. Output For each test case, print a line containing the test case number (beginning with 1) followed by the largest key prime that can be inferred from the clue C. If no key prime can be inferred, print ‘not

2/2 a valid clue’. (Dr. Wolf may make mistakes in Step 2, during the production of a clue.) Use the format of the sample output. Sample Input 6 112458 11 11122344457 3 189 4 4555 6 134568 -1 Sample Output Case 1: 17 Case 2: 29 Case 3: 17 Case 4: not a valid clue Case 5: not a valid clue