Alice 和 Bob 是赌徒。在等待进入赌场大厅时，他们开始掷硬币赌钱，直到其中一人破产为止。

起初，Alice 有 $a$ 美元，Bob 有 $b$ 美元。他们掷一枚硬币，如果结果是反面（tails），Alice 从 Bob 那里得到 $\min(a, b)$ 美元；否则（正面，heads），Bob 从 Alice 那里得到 $\min(a, b)$ 美元。如果其中一人输光了所有钱，他们就停止游戏并前往最近的自动取款机。否则，他们继续重复相同的过程。

例如，如果 Alice 有 $9$ 美元，Bob 有 $2$ 美元，过程可能如下：

在第 4 次掷硬币后，Bob 剩下 $0\$$，游戏结束。

大厅里的一些人开始对他们掷硬币直到其中一人破产所需的次数进行下注。你也想参与赌博，但首先，你必须计算掷硬币次数的期望值，以便做出明智的决定。

输入格式

第一行包含测试用例的数量 $Z$ ($1 \le Z \le 100\,000$)。接下来是各测试用例的描述。

每个测试用例仅包含一行，包含两个整数 $a, b$ ($1 \le a, b \le 10^{18}$)，分别表示 Alice 和 Bob 拥有的美元数量。

输出格式

我们可以证明所求的期望值总是一个有限的有理数。此外，当该值表示为不可约分数 $P/Q$ 时，我们可以证明存在唯一的整数 $R$，使得 $R \cdot Q \equiv P \pmod{998244353}$ 且 $0 \le R < 998244353$。

对于每个测试用例，请在一行中输出该整数 $R$。

样例

样例输入 1

2
1 1
3 9

样例输出 1

1
499122178

说明

在第一个测试用例中，Alice 或 Bob 在第一次掷硬币后就会输光所有钱。

在第二个测试用例中，掷硬币次数的期望值为 $1\frac{1}{2} \equiv 499122178 \pmod{998244353}$。