Description

There is $1$ yuan in the setter’s red packet, and he wants to randomly split this $1$ yuan among $n$ people.

To make it random, he designed the following algorithm to distribute it (in pseudocode):

a[0]=0,a[n]=1
for i=1 to n-1 do{
    a[i]=rand()
}
sort(a)
for i=1 to n do{
    money[i]=a[i]-a[i-1]
}

Here, the function rand() returns a real number uniformly at random in $[0,1]$, and the function sort() sorts an array in increasing order.

Now, the setter wants to know the expected value of the amount received by the person who gets the $k$-th smallest amount.

Since he wants to use this value to estimate how many red packets to send, he will ask you $T$ queries.

To avoid precision loss, output the answer modulo $998244353$.

To avoid excessive output, output the XOR sum of all answers.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, one line contains two integers $n, k$.

Output Format

Output one integer in a single line, representing the XOR sum of the answers to all queries.

3
1 1
2 2
2 1

574619649

Hint

[Sample Explanation]

For the first query, $n=k=1$, so the answer is $1$.

For the second query, the larger amount is uniformly distributed on $[\dfrac{1}{2},1]$, and its expectation is $\dfrac{3}{4}$, which becomes $249561089$ after taking modulo.

For the third query, the smaller amount is uniformly distributed on $[0,\dfrac{1}{2}]$, and its expectation is $\dfrac{1}{4}$, which becomes $748683265$ after taking modulo.

The XOR sum is $574619649$.

[Constraints]

This problem uses bundled testdata.

$\text{Subtask 1 (4 pts)}$: $n \le 10$, $k=1$.

$\text{Subtask 2 (16 pts)}$: $n \le 5 \times 10^3$.

$\text{Subtask 3 (20 pts)}$: $k=1$.

$\text{Subtask 4 (28 pts)}$: $n \le 10^5$.

$\text{Subtask 5 (32 pts)}$: no additional constraints.

For $100\%$ of the testdata, $1 \le k \le n \le 10^7$, $1 \le T \le 2 \times 10^5$.

Translated by ChatGPT 5