MAIN12D - Dice Problem

no tags 

Everyone loves Swampy. Swampy the Alligator lives under the city and yearns for a more human like existence. One day Swampy and his M friends decided to play a game. The game was simple. Everyone rolls an N-sided die and whoever gets the largest faced side wins. All the alligators lined up to throw the die. After all M friends of Swampy threw the die, it was Swampy's turn now to throw the die, but he being intelligent than the rest of his friends wanted to know for sure the odds of him winning the game.

Input

First line of the input contains an integer T, the number of test cases. Then T test cases follow. Each test case consists of two integers N and M. Next line contains M integers(space separated), d1, d2,..,dM, the face of the die Swampy's friends got.

Output

For each test case, print "Case #X: A/B" (quotes for clarity only), where X is the test case number starting from 1, A is the numerator, B is the denominator and A/B is in the form of an irreducible fraction. If the required probability equals to zero, output "0/1". If the required probability equals to 1, output "1/1".

Example

Input:
2
6 6
1 2 3 4 5 6
6 6
1 1 1 1 1 1

Output:
Case #1: 0/1
Case #2: 5/6

Constraints: T <= 100 1 <= N <= 1000 0 <= M <= 1000 1 <= di <= N


hide comments
parag agrawal: 2012-05-03 12:46:51

Last edit: 2012-05-03 12:47:56
Rishi Mukherje: 2012-04-30 08:33:31

I get NZEC in python. Is there some problem with the input file?

edit: ok, there is some problem with the input file..but
please clean the input file.

Last edit: 2012-04-30 16:30:08
Lars Krapf: 2012-04-24 18:19:19

Beware: If m == 0 then the test case consists of only 1 line.

neerajcrespo: 2012-04-11 14:04:31

any tricky case? for m=0, ans will always be 1/1 ain't it?
whats the o/p of
2 1
3
isn't it 0/1?

Jitesh: 2012-04-11 09:24:17

some more test cases please....

Ranker: 2012-04-08 06:07:17

easy Question but take care of the case m = 0.

time limit exceeded: 2012-04-06 14:14:12

more test cases please...

(Tjandra Satria Gunawan)(曾毅昆): 2012-04-06 11:08:41

easy :D

Rocker3011: 2012-04-03 02:01:08

good problem but with weak test cases ^^ not even had to validate 1/1 case (when i did i got WA XD)

spock: 2012-04-02 19:50:45

@andres
it should be 1/2


Added by:Nikunj Jain
Date:2012-03-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Vaibhav Mittal