BGC TRUST IUPC 2012

Problem C

Fisherman’s Dilemma

Your brother is playing a game. There is a tank full of live fishes. The tank has n x m cells and arranged in n rows and m columns. (1 <= n, m <= 200). Before each round, each cell is filled with a number of fishes (can be at most 20 in each cell). Those fishes don’t move much and stay in their own cells. His only tool is a rectangular trap. Its dimensions can be controlled (can have any positive integer dimension) and can be placed anywhere given that no part of your trap is outside the tank and no cell is partially covered. Your brother is very bad at setting traps and any of the possible top-left and bottom-right positions of the trap satisfying the aforementioned condition is equally likely. All his opponents have already attempted and the highest score among them is K <= 112500. He’ll have to score at least K to win (or tie for first place). What is the probability of this to happen?

Input

The input starts with a number T(<=50), denoting the number of test cases. T test cases will follow. Each test case starts with three integers n, m and K as mentioned in problem statement. n rows of m numbers will follow. j-th integer of i-th row will be the number of fishes in the cell at i-th row and j-th column.

Output

For each test case, print test case number and the probability as a reduced fraction. Reduced fraction means, if the probability is a / b, make sure that there is no common factor (greater than 1) between a and b. (Say the answer is 4/6, then you should print 2/3). The answer will always be positive. Refer to the sample output for exact format.

Sample Input	Output for Sample Input
1 2 8 76 15 1 10 5 19 19 3 5 6 6 2 8 2 12 16 3	Case 1: 13/108

Problemsetter: Mir Wasi Ahmed

Special Thanks: Abu Obaida