시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 3 3 100.000%

문제

Find the number of strings consisting of x letters ‘a’ and y letters ‘b’ that have the length of their longest substring consisting of equal letters as small as possible under these conditions, and display it modulo 998 244 353.

입력

The first line contains a single integer t (1 ≤ t ≤ 105), denoting the number of test cases.

Each of the next t lines describes one test case and contains two integers x and y (1 ≤ x, y ≤ 2000).

출력

For each test case, display the required number.

예제 입력 1

5
2 4
7 8
7 7
9 3
239 58

예제 출력 1

6
1
2
20
868098448

힌트

In the first test case, the strings are abbabb, bababb, babbab, bbaabb, bbabab, bbabba. In each of these strings, the length of the longest substring consisting of equal letters is 2, and there are no strings consisting of 2 letters ‘a’ and 4 letters ‘b’ with a smaller value.