描述

背景

二叉树是计算机科学中常见的数据结构。在这个问题中，我们将研究一棵无限二叉树，其节点包含一对整数。这棵树的构建方式如下：

• 根节点包含数对$(1, 1)$。
• 如果一个节点包含$(a, b)$，那么它的左子节点包含$(a + b, b)$，右子节点包含$(a, a + b)$。

问题

给定上述二叉树中某个节点的内容$(a, b)$，假设你从树的根节点沿着最短路径走到给定节点。你能计算出需要向左子节点走多少次，向右子节点走多少次吗？

输入

第一行包含测试用例的数量。

每个测试用例由单独的一行组成，包含两个整数$i$和$j$（$1 \leq i, j \leq 2\times10^{9}$），它们表示一个节点$(i, j)$。你可以假设这是上述二叉树中的一个有效节点。

输出

每个测试用例的输出以一行 “Scenario #i:” 开头，其中$i$是从1开始的测试用例编号。然后打印一行，包含两个用单个空格分隔的数字$l$和$r$，其中$l$是从根节点遍历到输入中给定节点时向左走的次数，$r$是向右走的次数。每个测试用例输出后打印一个空行。

输入数据1

3
42 1
3 4
17 73

输出数据1

Scenario #1:
41 0

Scenario #2:
2 1

Scenario #3:
4 6

来源

2005年德国达姆施塔特工业大学编程竞赛（训练赛）