Alice 和 Bob 喜欢涉及随机数的问题。一天，他们想出了以下问题：

• 首先，Alice 从 $1$ 到 $2^{31} - 1$ 的范围内随机选择一个整数 $x$，所有数字被选中的概率均等。
• 然后，Bob 从 $1$ 到 $2^{31} - 1$ 的范围内随机选择一个整数 $y$，所有数字被选中的概率均等。
• 他们计算这两个数的乘积 $a = x \cdot y$ 以及它们的按位异或值 $b = x \oplus y$。

给你两个得到的整数 $a$ 和 $b$。请找到任意一对自然数 $x$ 和 $y$，满足：

$$xy = a \quad \text{且} \quad x \oplus y = b$$

其中 $\oplus$ 表示按位异或（XOR）操作。

请注意，两个非负整数的按位“异或”（$\oplus$，xor）定义如下：将两个数写成二进制表示；如果两个数中恰好有一个数的第 $i$ 位二进制位为 $1$，则结果的第 $i$ 位二进制位为 $1$。例如，$(14 \text{ xor } 7) = (1110_2 \oplus 0111_2) = 1001_2 = 9$。该操作在所有现代编程语言中均有实现；在 C++、Java 和 Python 中，它被写作 ^，在 Pascal 中被写作 xor。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 200\,000$) —— 测试用例的数量。

接下来的 $t$ 行中，每行包含两个整数 $a$ 和 $b$ ($1 \le a < 2^{62}$，$0 \le b < 2^{31}$) —— 对应测试用例的描述。

输出格式

对于每个测试用例，在单独的一行中输出两个用空格隔开的自然数 $x$ 和 $y$，使得 $xy = a$ 且 $x \oplus y = b$。

如果存在多个有效答案，你可以输出其中任意一个。

样例

输入样例 1

2
21 4
9 0

输出样例 1

7 3
3 3

说明

在本题中，共有 100 个测试点（包括样例）。保证在除样例外的所有测试点中，$t = 200\,000$，且每个测试用例中的数字 $a$ 和 $b$ 都是由 Alice 和 Bob 随机选择数字 $x$ 和 $y$ 生成的。