PONY5 - Teaming up for the competition

Since the Iron Pony competition was such fun last year, the ponies have decided to host a similar event this year, but this time it would be in teams. When each pony arrives at the event, they receive a number between 1 and 10^18. It is possible that some ponies receive the same number. Once every pony arrives, Miss Mayor will announce a number X and how to determine which team a pony is on - the pony takes their given number and looks at the result modulo X. That is their team number.

Dr. Whooves is at the event with a group, and he was wondering about the numbers X that would let his entire group be on the same team. Dr. Whooves likes big numbers, so he is going to suggest to Miss Mayor the number X which is the largest number that would let his entire group be on the same team.

Your goal is to determine what number Dr. Whooves suggested to Miss Mayor. But because the number might be really big, if there is a valid X larger than 10^18, just print "I can't count that high".

Input

The input will contain one line with a number T, the number of test cases in the file.

On the next T lines, one for each of the cases. The format of the case is "Case #i: N a1 a2 ... aN" where N is the number of ponies in Dr. Whooves's group, and each a_j is the number given to a pony in his group.

Output

There will be T lines in your output, one for each of the test cases in the input. The output format for case i is "Case #i: X" where X is the number that Dr. Whooves suggests to Miss Mayor, unless X is too large, and then you print "I can't count that high" [see sample output]

Example

Input:
2
Case #1: 3 178 928 440
Case #2: 1 1000000000000000000

Output:
Case #1: 2
Case #2: I can't count that high

Limits

1 <= N <= 1000000 (10^6)
Warning: Large input files

Added by:Alex Anderson
Date:2012-06-21
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:My own problem

hide comments
2012-09-27 06:01:06 Problem Solver
Hey Alex, could you look up at my solution? I have no idea why i got WA

EDIT: I've looked, and you seem to have the right idea, but a few implementation bugs. A lot of the time, you are getting very small answers, when the actual answer is instead very large. Other times when the answer should be "I can't count that high" you still output a value.

Last edit: 2012-10-06 03:42:32
2012-06-24 07:21:06 Ehor Nechiporenko
What a nice problem. Module arithmetics rules!
2012-06-22 19:02:08 Pranay
EDIT by Alex: Try solving the case when N = 2 and see what happens.
--> Thanks, i tried for N =2 and id = 5,6 and got 1 which i think is correct (7198380)
EDIT by Alex: I meant, try solving the case when N = 2, and for all possible ids that could be given.

Last edit: 2012-06-28 04:34:09
2012-06-22 17:13:06 15972125841321
nice question .. :) nice logic with the range involved ;)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.