题目背景

$\mathbf{000111}$，这就是简单中所蕴含的优美。

众所周知，tlx 不会字符串。

题目描述

现在 tlx 有 $n$ 个 $\mathbf{1}$ 和 $m$ 个 $\mathbf{0}$，你需要把它们排列，但要保证任意的 $\mathbf{1}$ 互不相邻且第一个位置是 $\mathbf{0}$、最后一个位置是 $\mathbf{1}$，现在把所有可以构造出的串放到一棵 0-1 Trie 上，需要多少个节点？

注意：节点计数时，不计算最开始的空节点，只计算代表“ $\mathbf{0}$ ”、“ $\mathbf{1}$ ”的节点。

在本题中，我们认为用节点存储字符而非边， Trie 基本原理不变。

因为答案可能很大而且询问较多，所以请在最后输出所有询问的答案对 $18888913$ （放心，是个质数）取模的结果的异或和（异或和不再进行取模）。

输入格式

第一行是一个正整数 $T$，代表数据组数。

接下来 $T$ 行，每行两个正整数 $n,m$，分别代表 $\mathbf{1,0}$ 的个数。

输出格式

共一行一个整数，代表所有结果的异或和。

1
2 4

15

2
3 5
114514 1919810

4487351

5
78 122
1000000 1000001
74859432 942432534
555555555 77777777 
6666666666 8888888888

12287990

提示

【样例解释 #1】

可以发现，所有能构造出的串有：

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

构造 0-1 Trie，如图：

共需 $15$ 个节点。

【样例解释 #2】

两次询问的答案分别为 $34$ 和 $4487317$。

---

【数据规模与提示】

注意：本题采用捆绑测试，只有当你通过一个 Subtask 内的所有测试点后，你才能拿到这个 Subtask 的分数。

具体约束如下：

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\%$）：无特殊限制。

对于 $100\%$ 的数据，满足 $1\le T \le 2\times10^6$，$1\le n,m\le 5\times 10^{18}$。

本题输入量较大，建议采用较为快速的读入方式并注意常数因子对程序效率带来的影响。

---

0-1 Trie 是一种特殊的 Trie ，只有 $\mathbf{0,1}$ 两种字符。

如果你不了解 Trie，可以查看：OI Wiki--Trie。