How can I believe in God when just last week I got my tongue caught in the roller of an electric typewriter?

Woody Allen

A roller coaster has n seats. There is a queue of people waiting to ride it. The queue is a sequence of groups of people. Each group wants to ride the roller coaster together. Of course, groups that have more than n people must be split up, but smaller groups must stay together. Each group occupies consecutive slots in the queue, and to be fair, no one must wait longer than anyone further back in the queue. In other words, we will load people in queue order.

The performance of the roller coaster is the ratio of the average number of occupied seats to the total number of seats, n. What is the worst possible average performance, as time goes to infinity? Assume that the queue is infinite.

Input
The input starts with a line giving the number of test cases, N. N lines follow. Each one contains a positive integer n (at most 10,000).

Output
For each test case, output one line containing "Case #x:" followed by the worst possible performance, as a fraction in lowest terms.

3
1
2
3

Case #1: 1/1
Case #2: 3/4
Case #3: 2/3