1225:又一个子序列问题

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

6
1 1
3 5
4 7
8 20
4 10
27 21
##CASE##
18
5 9
23 30
820 483
5739 9232
86494 55350
606 13336
2768848 1124639
47995594 66053082
1069395 7177
7801842511 4390103762
47882886553 82678306054
193410894 6189355686
51594638 19992922190
59 110
422735115778072 658356435030265
9125338158530266 5328357177709583
60743352262021049 95595862538791630
629312141725417942 999581828389011547

Hint

Source