PRIMEZUK - The Prime conjecture

no tags 

Euclid may have been the first to prove that there are infinitely many primes. Let's walk through his proof, as even today, it's regarded as an excellent model of reasoning.

Let us assume the converse, that there only a finite number of primes: p1, p2, ... pn. Let m = 1 + i=1Πn pi, i.e. the product of all of these primes plus one. Since this number is bigger than any of the primes on our list, m must be composite. Therefore, some prime must divide it. But which prime? In fact, m leaves a reminder of 1 when divided by any prime pi, for 1 <= i <= n. Thus, p1, p2, ... pn cannot be the complete list of primes, because if so m must also be a prime. Since this contradicts the assumption it means there cannot exist such a complete list of primes; therefore the number of primes must be infinite!

Your mathematician friend Wannabe_Fermat has come up with a conjecture which he keeps telling to anyone who is willing to lend an ear: "The number m that we come up with when multiplying any n distinct prime numbers and adding 1 to this result is also a prime". You as Wannabe_Zuckerburg, are becoming jealous as your friend's conjecture is gaining popularity and decide to come up with a program that finds counter-examples to shut him up forever.

Input

The first line contains T, the number of test cases. Each test case consists of two lines, the first line containing the number n - the number of primes in our list, and second line containing n space-separated prime numbers. Moreover, following things can be safely assumed:

1 <= T <= 10

n will be at most 9 and m can be contained in 32-bits.

Output

For each input case x, the output is of the format "Case #x: y", where y = m if m is a prime, else y is the largest prime factor of m.

Example

Input:
2
3
2 3 5
4
2 7 5 11

Output:
Case #1: 31
Case #2: 257

Explanation

Case #1 - 31 is a prime number

Case #2 - 2*5*7*11 + 1 = 771, which can be written as 3*257.


hide comments
Himanshu: 2013-06-15 09:32:27

a optimized naive algorithm got AC in 0.01 sec.......thanks to FLT....

Kousik Kumar: 2013-06-07 06:43:02

Some corner cases if you had made some assumptions about the question:

1
7
2 3 5 7 11 13 23
Ans: 4969

You can naively find the largest prime factor of the product. No short cuts.

Jakub ©imek: 2013-06-05 14:57:59

Cool problem statement, very easy problem :)
Even pretty naive algorithm got AC in 0.00

Anuj_LuckFove!: 2013-05-31 18:44:54

easy one :) and there is no problem in the constraints given...'int' worked well for me in C

Last edit: 2013-05-31 18:45:49
[Lakshman]: 2013-05-23 16:46:41

Nice problem.

time limit exceeded: 2012-08-26 07:03:54

awesome description......

Snehasish Roy ;): 2012-08-17 20:15:58

Piece of cake :D

Santhana Krishnan: 2012-04-08 14:45:40

I am curious to know what folks find more interesting in this problem compared to other prime number related ones in SPOJ. To me this seems similar to many others although I don't mind number theory problems.

Last edit: 2012-04-08 14:46:04
Rajkiran Rajkumar: 2011-11-19 16:25:38

Some test cases please?

johnny bravo: 2011-10-12 13:26:57

A great problem statement...
Was fun doing.

Last edit: 2011-10-12 13:27:38

Added by:Siddharth Kothari
Date:2011-09-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own