题目描述Description

对于任意两个正整数 \(a\) 和 \(b\)，根据以下 C++ 代码定义函数：

std::string gen_string(int64_t a, int64_t b) {
  std::string res;
  int64_t ia = 0, ib = 0;
  while (ia + ib < a + b) {
    if ((__int128)ia * b <= (__int128)ib * a) {
      res += '0';
      ia++;
    } else {
      res += '1';
      ib++;
    }
  }
  return res;
}

当循环终止时，\(ia\) 将等于 \(a\)，\(ib\) 将等于 \(b\)，因此该函数会返回一个长度为 \(a+b\) 的 \(01\) 字符串，其中恰好有 \(a\) 个 \(0\) 和 \(b\) 个 \(1\)。

例如，\(gen\_string(4,10)=01110110111011\)。

给定参数 \(A, B\)，你需要计算 \(gen\_string(A, B)\) 的本质不同的子序列的数量，并将答案对 \(998244353\) 取模后输出。

注意：序列 \(a\) 是字符串 \(b\) 的子序列，当且仅当 \(a\) 可以通过删除 \(b\) 中的若干（可能为零或全部）元素得到。

输入格式Input

第一行包含一个整数 \(T\ (1\le T\le 100)\)，表示测试用例的数量。

接下来的 \(T\) 行，每一行包含两个整数 \(A\) 和 \(B\) (\(1\le A,B \le 10^{18}\))，意义如题面所述。

输出格式Output

对于每个测试用例，输出 \(gen\_string(A, B)\) 的不同子序列的数量，对 \(998244353\) 取模后输出。

样例Sample

出题Author

SYSU

来源Source