Background

$\mathbf{000111}$, this is the beauty contained in simplicity.

As everyone knows, tlx cannot handle strings.

Problem Description

Now tlx has $n$ $\mathbf{1}$'s and $m$ $\mathbf{0}$'s. You need to arrange them, but you must ensure that any two $\mathbf{1}$'s are not adjacent, and that the first position is $\mathbf{0}$ and the last position is $\mathbf{1}$. Now put all strings that can be constructed onto a 0-1 Trie. How many nodes are needed?

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

In this problem, we assume characters are stored in nodes rather than on edges, but the basic idea of the Trie is unchanged.

Because the answer may be very large and there are many queries, please finally output the XOR sum of all query answers modulo $18888913$ (don’t worry, it is a prime). (The XOR sum itself is not taken modulo again.)

Input Format

The first line is a positive integer $T$, representing the number of test cases.

In the next $T$ lines, each line contains two positive integers $n, m$, representing the counts of $\mathbf{1}$ and $\mathbf{0}$ respectively.

Output Format

Output one integer in a single line, representing the XOR sum of all results.

1
2 4

15

2
3 5
114514 1919810

4487351

5
78 122
1000000 1000001
74859432 942432534
555555555 77777777 
6666666666 8888888888

12287990

Hint

[Sample Explanation #1]

We can see that all constructible strings are:

Construct the 0-1 Trie as shown:

A total of $15$ nodes are needed.

[Sample Explanation #2]

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

[Constraints and Hints]

Note: this problem uses bundled testdata. You will only get the score of a Subtask after you pass all test points within that Subtask.

The specific constraints are as follows:

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

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

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

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

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

The input size of this problem 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 kind of Trie with only two characters, $\mathbf{0,1}$.

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

Translated by ChatGPT 5