Trie Nodes Count from Non‐adjacent Ones Strings

Consider the following problem. We are given two nonnegative integers $n$ and $m$ such that we have exactly $n$ copies of $\mathbf{1}$ and $m$ copies of $\mathbf{0}$. You are to arrange all these digits to form a binary string of length $n+m$ subject to the following conditions:

1. The first character is $\mathbf{0}$.
2. The last character is $\mathbf{1}$.
3. No two $\mathbf{1}$'s are adjacent.

Let $S$ be the set of all strings (if any) satisfying the above conditions. Now, insert every string in $S$ into a 0-1 trie (a tree structure in which each node stores a character, either $\mathbf{0}$ or $\mathbf{1}$). We do not count the initial empty node; only nodes representing a character are counted. Your task is to determine the number of nodes in the trie built from $S$.

Note: Since the answer for some instances might be very large and there may be many queries, for each query compute the answer modulo $18888913$ (which is prime) and then output the bitwise XOR (i.e. ^ in many languages) of all these modulo results. The final XOR is not taken modulo $18888913$.

---

Explanation: A valid string $T$ of length $L=n+m$ must satisfy

[ T_1=0, \quad T_L=1, \quad \text{and for every } 1 \le i < L,; T_i=1 ;\Rightarrow; T_{i+1}=0. ]

All valid strings in $S$ are inserted into a trie. A node is created for every distinct nonempty prefix that appears in at least one string in $S$. Your task is to count these nodes.

---

Input/Output format: See below.

inputFormat

The first line contains an integer T (T > 2) indicating the number of test cases.

Each of the following T lines contains two integers n and m separated by a space, representing the number of 1's and 0's respectively. It is guaranteed that at least one valid string can be constructed.

outputFormat

Output a single integer — the XOR (bitwise exclusive‐or) of the answers for all test cases, where for each test case the answer is the number of nodes in the trie (built from all valid strings) taken modulo 18888913.

sample

3
1 1
2 3
3 4

11

</p>