Problem Background

$\mathbf{000111}$, this is the elegance hidden in simplicity.

As everyone knows, tlx is not good with strings.

Problem Description

tlx has $n$ $\mathbf{1}$'s and $m$ $\mathbf{0}$'s. You need to arrange them such that no $\mathbf{1}$'s are adjacent and the first position is $\mathbf{0}$ and the last position is $\mathbf{1}$. Now, place all constructible strings on a 0-1 Trie. How many nodes are needed?

Note: When counting nodes, do not count the initial empty node, only count nodes representing "$\mathbf{0}$" and "$\mathbf{1}$".

In this problem, we consider storing characters in nodes rather than edges, with the basic principles of Trie remaining unchanged.

Since the answer may be very large and there are many queries, output the XOR sum of the answers modulo $18888913$ (don't worry, it's a prime number) for all queries (the XOR sum is not moduloed again).

Input Format

The first line is a positive integer $T$, representing the number of data sets.

The next $T$ lines each contain two positive integers $n, m$, representing the number of $\mathbf{1}$'s and $\mathbf{0}$'s, respectively.

Output Format

A single line with an integer representing the XOR sum of all results.

Sample Input and Output

Sample Input #1

1
2 4

Sample Output #1

15

Sample Input #2

2
3 5
114514 1919810

Sample Output #2

4487351

Sample Input #3

5
78 122
1000000 1000001
74859432 942432534
555555555 77777777
6666666666 8888888888

Sample Output #3

12287990

Notes

[Sample Explanation #1]

It can be found that all constructible strings are:

$$\mathbf{000101}$$
$$\mathbf{001001}$$
$$\mathbf{010001}$$

Constructing a 0-1 Trie, as shown in the figure:

A total of $15$ nodes are needed.

[Sample Explanation #2]

The answers for the two queries are $34$ and $4487317$, respectively.

[Data Size and Hints]

Note: This problem uses bundled testing. You can only get the score for a Subtask if you pass all test points within that Subtask.

Specific constraints are as follows:

Subtask $1$ ($10\%$): Satisfies $T \leq 10$, $n, m \leq 5$;

Subtask $2$ ($20\%$): Satisfies $T \leq 10$, $n, m \leq 1 \times 10^3$;

Subtask $3$ ($30\%$): Satisfies $T \leq 10$, $n, m \leq 5 \times 10^5$;

Subtask $4$ ($40\%$): No special restrictions.

For $100\%$ of the data, satisfies $1 \le T \le 2 \times 10^6$, $1 \le n, m \le 5 \times 10^{18}$.

The input size is large, it is recommended to use a fast input method and pay attention to the impact of constant factors on program efficiency.

A 0-1 Trie is a special type of Trie that only contains the characters $\mathbf{0}$ and $\mathbf{1}$.

If you are not familiar with Trie, you can refer to: OI Wiki--Trie.

见题面 Input 部分

见题面 Output 部分