You are given two strings $$$u$$$ and $$$v$$$. In one operation, exactly one of the following modifications can be applied to the current string:
An operation is determined by its type, its position at the moment it is performed, and its inserted or replacement character when applicable. Two operation sequences are different if their lengths differ or if their operations differ at some step. Thus, applying the same modifications in different orders may produce different operation sequences.
Count the minimum-length operation sequences that transform $$$u$$$ into $$$v$$$, modulo $$$998~244~353$$$.
Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 5~000$$$). The description of the test cases follows.
The first line of each test case contains a non-empty string $$$u$$$ ($$$1 \le |u| \le 5~000$$$) consisting of lowercase English letters.
The second line contains a non-empty string $$$v$$$ ($$$1 \le |v| \le 5~000$$$) consisting of lowercase English letters.
It is guaranteed that the sum of $$$|u|$$$ over all test cases does not exceed $$$5~000$$$, and the sum of $$$|v|$$$ over all test cases does not exceed $$$5~000$$$.
For each test case, output the number of minimum-length operation sequences that transform $$$u$$$ into $$$v$$$, modulo $$$998~244~353$$$.
2 ab ba paper pepper
6 6
In the first test case, the minimum number of operations is $$$2$$$. There are three optimal alignments: replace both characters; delete the first character and append it; or insert b at the beginning and delete the last character. The two operations for each alignment can be performed in either order, giving $$$3 \cdot 2! = 6$$$ operation sequences.
