Time Limit: 1 sec
Memory Limit: 32 MB
John has been given a segment of lenght N, however he needs a polygon. In order to create a polygon he has cut given segment K times at random positions (uniformly distributed cuts). Now he has K+1 much shorter segments. What is the probability that he can assemble a polygon using all new segments?
The number of tests T
(T ≤ 1000) is given on the first line. T
lines follow,
each of them contains two integers N K
(1 ≤ N ≤ 106; 1 ≤ K ≤ 50) described
above.
For each test case output a single line "Case #T: F"
. Where T
is the test case number
(starting from 1) and F
is the result as simple fraction in form of N/D
. Please refer
to the sample output for clarity.
2 1 1 2 2
Case #1: 0/1 Case #2: 1/4