New Year's Eve Wine Pyramid

Time limit5sMemory limit512 MB

Summary
Wine poured into the top glass of a pyramid of glasses overflows in equal thirds to the level below, and each query asks how much one glass holds.
Level

Medium4 of 10

Topics
Simulation
Solved
No attempts yet

Problem

Wine glasses are stacked in a pyramid at a new year's party. The top level holds one glass, the level below it holds three, the next holds six, and the one after that holds ten. The picture below shows the shape.

A glass is identified by two numbers, LL and NN. LL is the level the glass sits on and NN is the number of the glass inside that level. Glasses on a level are numbered like this:

Level 1:
    1

Level 2:
    1
 2     3

Level 3:
      1
   2     3
4     5     6

Level 4:
         1
      2     3
   4     5     6
7     8     9     10

Level LL is a triangle of rows holding 1 glass up to LL glasses, so it has L(L+1)2\frac{L(L+1)}{2} glasses. The glass in position jj of row ii has number i(i−1)2+j\frac{i(i-1)}{2} + j.

Each glass holds 250ml of wine. The bartender pours wine into the top glass (L=1L = 1, N=1N = 1) from bottles of 750ml each.

Once a glass is full, the wine that no longer fits overflows in equal parts into the three glasses of the next level that touch it, and nothing is spilled outside. Wine never overflows sideways into a glass on the same level, and it never falls straight past the next level. Wine that overflows from the glass in position jj of row ii on level LL reaches position jj of row ii, position jj of row i+1i+1, and position j+1j+1 of row i+1i+1 on level L+1L+1. For example, when the glass with L=2L = 2 and N=2N = 2 overflows, the wine reaches the glasses with L=3L = 3 and NN equal to 2, 4 and 5.

After the bartender has poured all BB bottles, find how much wine in ml the glass with number NN on level LL holds.

Input

The first line has the number of test cases, TT. TT test cases follow. Each test case is three integers BB, LL and NN. BB is the number of bottles the bartender pours, LL is the level the glass sits on and NN is the number of the glass inside that level.

Output

For each test case print one line in the form "Case #x: y", where xx is the test case number starting from 1 and yy is the amount of wine in ml in that glass. Round yy to seven decimal places and print all seven digits, including trailing zeros.

Constraints

  • 1≤T≤1501 \le T \le 150
  • 1≤B≤10001 \le B \le 1000
  • 1≤L≤1001 \le L \le 100
  • 1≤N≤L(L+1)21 \le N \le \frac{L(L+1)}{2}

Examples2

  1. Example 1

    Input
    7
    1 2 1
    1 1 1
    2 1 1
    20 1 1
    1 3 1
    2 3 1
    10 4 10
    
    Expected output
    Case #1: 166.6666667
    Case #2: 250.0000000
    Case #3: 250.0000000
    Case #4: 250.0000000
    Case #5: 0.0000000
    Case #6: 55.5555556
    Case #7: 157.4074074
    
  2. Example 2

    Input
    7
    3 2 1
    3 2 2
    3 2 3
    3 3 1
    3 3 4
    3 3 5
    3 4 5
    
    Expected output
    Case #1: 250.0000000
    Case #2: 250.0000000
    Case #3: 250.0000000
    Case #4: 138.8888889
    Case #5: 138.8888889
    Case #6: 250.0000000
    Case #7: 27.7777778