题目描述

考虑一棵无限完全二叉树，其中根节点为 $1/1$，节点 $p/q$ 的左子节点和右子节点分别为 $p/(p+q)$ 和 $(p+q)/q$。这棵树如下图所示：

:::align{center} :::

已知每个正有理数在这棵树中恰好出现一次。对这棵树进行层序遍历，得到如下序列：

$1/1$, $1/2$, $2/1$, $1/3$, $3/2$, $2/3$, $3/1$, $\dots$

请解决以下两个问题：

1. 找到序列中的第 $n$ 个元素，其中 $n$ 从 $1$ 开始。例如，对于输入 $2$，正确的输出是 $1/2$。
2. 给定 $p/q$，找到它在序列中的位置。例如，输入 $1/2$ 会得到输出 $2$。

输入格式

第一行输入包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例占一行，包含一个问题编号（$1$ 或 $2$）以及一个或两个额外的整数：

1. 如果问题编号为 $1$，则只给出一个整数 $n$，你需要找到序列中的第 $n$ 个元素。
2. 如果问题编号为 $2$，则给出两个整数 $p$ 和 $q$，你需要找到 $p/q$ 在序列中的位置。

输出格式

对于每个测试用例：

1. 如果问题编号为 $1$，则输出一行形如 "Case #x: p q" 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$p, q$ 分别是所求序列元素的分子和分母。
2. 如果问题编号为 $2$，则输出一行形如 "Case #x: n" 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$n$ 是给定数字的位置。

4
1 2
2 1 2
1 5
2 3 2

Case #1: 1 2
Case #2: 2
Case #3: 3 2
Case #4: 5

提示

限制

$1 \le T \le 100$；$p$ 与 $q$ 互质。

测试集 1 - 可见

$1 \le n, p, q \le 2^{16}-1$；$p/q$ 是层编号不超过 $16$ 的树中的元素。

测试集 2 - 隐藏

$1 \le n, p, q \le 2^{64}-1$；$p/q$ 是层编号不超过 $64$ 的树中的元素。

翻译由 DeepSeek V4 Pro 完成