100 人解决，118 人已尝试。
114 份提交通过，共有 236 份提交。
2.8 EMB 奖励。
10. Bob and a Binary tree
单点时限: 2.0 sec
内存限制: 256 MB
现有一个无限的完全二叉树，每个节点上都标有一个有理数。定义如下：
-
根节点上的有理数是
1/1。 -
p/q左儿子节点的标记是p/(p+q)。 -
p/q右儿子节点的标记是(p+q)/q。
如图所示：
按照图示箭头方向，可以遍历得到一个有理数序列：
F(1) = 1/1, F(2) = 1/2, F(3) = 2/1, F(4) = 1/3, F(5) = 3/2, F(6) = 2/3, ...
本题任务是给定 (n)，计算 (F(n))。
输入格式
第一行是一个整数 (T)，((1 \leq T \leq 100))，表示测试数据组数。
每组测试数据有一行一个整数 (N)，((1 \leq N \leq 2147483647))。
对于约 10% 的数据，有 (1 \leq T \leq 10)。
对于约 30% 的数据，有 (1 \leq N \leq 10^7)。
输出格式
对于每组测试数据，输出一行形如：Case i: p/q 表示答案。
样例
Input
4 1 4 11 1431655765
Output
Case 1: 1/1 Case 2: 1/3 Case 3: 5/2 Case 4: 2178309/1346269
题目标签