我丢斯尼

题目描述

Farmer John 和 Bessie 正在玩一个石头游戏。

初始时，Farmer 手中有 $x$ 块石头，Bessie 有 $y$ 块。他们的眼前有一个石头堆，可以认为里面有无限块石头。

从 Farmer John 开始，双方轮流操作。每次操作中，如果自己的石头数量小于对方的石头数，就从石头堆中拿 $1$ 块石头；否则，就要向石头堆里扔石头直到手中的石头数不超过本次操作开始时自身石头数的一半（这就是说，如果本次操作开始时自己有 $w$ 块石头，则需要扔石头直到手里还剩 $\left\lfloor\frac w 2 \right\rfloor$ 块石头）。当有一方在操作完成后手头没有石头（即石头数量为 $0$）了，那么游戏结束。

请你求出游戏结束时双方手中的石头数量。

输入格式

本题单个测试点内有多组测试数据。

第一行是一个整数，表示数据组数 $T$。接下来 $T$ 行，每行表示一组数据的输入信息。

对每组数据，输入只有一行两个整数，依次表示 Farmer John 初始的石头数 $x$ 和 Bessie 初始的石头数 $y$。

输出格式

对每组数据，输出一行两个整数，依次表示 Farmer John 最终的石头数 $x$ 和 Bessie 最终的石头数 $y$。

样例 #1

样例输入 #1

1
2 5

样例输出 #1

0 1

提示

样例 1 解释

下表中，用 $s$ 和 $t$ 分别代表 Farmer John 和 Bessie 在对应轮次开始前手中的石头数，每行代表一次操作。

数据规模与约定

• 对 $20\%$ 的数据，保证 $x, y \leq 5$。
• 另有 $20\%$ 的数据，保证 $x = y$。
• 对 $60\%$ 的数据，保证 $x, y \leq 10^9$，$T = 1$。
• 对 $100\%$ 的数据，保证 $1\leq T \leq 100$，$1 \leq x, y \leq 10^{18}$。

provider：一扶苏一