L. Station of Fate
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ people standing in $$$m$$$ stations, forming $$$m$$$ queues.

You don't know which person is in which station, or in what order they are standing in queue, so you want to count the number of different schemes. Two schemes are considered different, if and only if there exists a station whose queue consists of different people, or has different orders.

Calculate the number of different schemes modulo $$$998\, 244\, 353$$$.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le 100$$$), denoting the number of test cases. Then $$$T$$$ test cases follow.

Each test case contains a single line containing two integers $$$n, m$$$ ($$$1 \le m \le n \le 10^5$$$).

Output

For each test case, output the number of different schemes modulo $$$998\, 244\, 353$$$.

Example
Input
2
3 2
6 3
Output
12
7200