P7386 "EZEC-6" 0-1 Trie

> $\mathbf{000111}$, this is the beauty contained in simplicity. As everyone knows, tlx cannot handle strings.

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.**)

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 one integer in a single line, representing the XOR sum of all results.

**[Sample Explanation #1]** We can see that all constructible strings are: $$\mathbf{000101}$$ $$\mathbf{001001}$$ $$\mathbf{010001}$$ 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](https://deploy-preview-980--oi-wiki.netlify.app/string/trie/). Translated by ChatGPT 5