MAIN12D - Dice Problem

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


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

hide comments
2012-04-01 15:05:28 Andres Eloy Fernandes
In this case: 6 3, 1 2 3, what's the correct answer?
2012-03-31 08:09:36 Aradhya
tutorial ... for kids!!!
2012-03-28 22:35:26 shivamrana
after some silly mistakes, finally got AC.. :D
2012-03-28 04:15:29 Devil D
ya pretty easy i guess.. tutorial or not, not sure

Last edit: 2012-03-28 04:15:41
2012-03-25 00:52:49 :D
Should be moved to tutorial.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.