hackercupai/hackercup huggingface dataset:
Let **S** be a sequence of **N** natural numbers. We can define an infinite
sequence **MS** in the following way: **MS**[k] = **S**[k mod **N**] + **N** *
floor(k / **N**). Where k is a zero based index.

For example if the sequence **S** is {2, 1, 3} then **MS** would be {2, 1, 3,
5, 4, 6, 8, 7, 9, 11, 10, 12...}

Now consider a subsequence of **MS** generated by picking two random indices
**a**, **b** from the range [**0**..**R**] inclusive, and taking all the
elements between them, that is: **MS**[min(**a**, **b**)..max(**a**, **b**)].

If we use the same **MS** as in the example above and **a** = 2, **b** = 5
then our subsequence would be {3, 5, 4, 6}.

Your task is to calculate the probability that the selected subsequence has at
least **K** distinct elements. **a** and **b** are selected independently and
with a uniform distribution. The result should be printed as a fraction. See
the "Output" section for clarification.

### Input

The first line of the input file contains an integer **T**. This is followed
by **T** test cases, each of which has two lines.

The first line of each test case contains three integers separated by spaces,
**N**, **K**, and **R**.

The second line contains **N** space separated integers, **S**[0] through
**S**[**N**-1].

### Constraints

1 ≤ **T** ≤ 20
1 ≤ **N** ≤ 2,000
1 ≤ **K** ≤ **R** ≤ 1,000,000,000
1 ≤ **S**[i] ≤ 100,000

### Output

For each of the test cases numbered in order from 1 to **T**, output "Case
#**i**: " followed by the probability that the selected subsequence of **MS**
has at least **K** distinct elements. The probability should be expressed as a
fraction **p**/**q**, where **p** and **q** represent the numerator and
denominator respectively and are relatively prime (that is they share no
common positive divisors except 1).

If the probability is 0 or 1 output 0/1 or 1/1 respectively.

### Examples

In the first example there are 36 different subsequences to consider. 6 of
them have only a single number, and the remaining 30 have at least 2 different
numbers, so the answer is 5/6.

The second example is similar, but now the sequence looks like {2, 1, 5, 5, 4,
8}. There are 8 subsequences with less than 2 distinct numbers: the six single
number subsequences plus (a=2, b=3) and (a=3, b=2) which both result in {5,5}.
That gives a probability of (36 - 8) / 36 = 7/9.

The third example uses the same sequence as the second example, but now we
want to have subsequences with at least 4 different numbers. All pairs of
indices that have this property are: (0,4), (0, 5), (1, 5), (4, 0), (5, 0),
and (5, 1). Six out of thirty six results in a probability of 1/6.