Kilk

각 x, y에 대해 a가 x개, b가 y개인 문자열 중 같은 문자가 연속된 가장 긴 부분 문자열의 길이가 최소가 되는 문자열의 개수를 998244353으로 나눈 나머지를 구한다.

어려움8조합론수학동적 계획법문자열아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제1

문제

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.

힌트

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.