给定非负整数 $A, B$，定义有序非负整数对 $(x, y)$ 为好的当且仅当：
- $0 \le x \le y$；
- $x + y = A$；
- $x \operatorname{AND} y = B$。
其中 $\operatorname{AND}$ 代表按位与运算。在 C++ 语言中由 `&` 运算符表示。
你需要求出所有好的有序非负整数对 $(x, y)$ 的 $y - x$ 的和。
由于该值可能很大，你只需要输出其对 $M$ 取模后的结果。
形式化的，你需要求出
$$\left(\sum\limits_{x \ge 0}\sum\limits_{y \ge 0}\left(y - x\right)\left[\operatorname{good}(x, y)\right]\right)\bmod M$$
其中 $\operatorname{good}(x, y)$ 为真与有序非负整数对 $(x, y)$ 为好的等价。
## Input
**本题单个测试点内含有多组询问。**
第一行两个整数 $T, M$，分别代表询问组数和模数。
接下来 $T$ 行，每行两个非负整数 $A, B$，代表一组询问。
## Output
对于每组测试数据，输出一行一个整数，代表答案。
[samples]
## Note
**【样例 #1 解释】**
对于第一组询问，好的数对有 $\left(1, 7\right)$ 和 $\left(3, 5\right)$，因此答案为 $\left(7 - 1\right) + \left(5 - 3\right) = 8$。
对于第二组询问，好的数对只有 $\left(4, 6\right)$，因此答案为 $6 - 4 = 2$。
对于第三组询问，好的数对有 $\left(0, 6\right)$ 和 $\left(2, 4\right)$，因此答案为 $\left(6 - 0\right) + \left(4 - 2\right) = 8$。
**【样例 #2 解释】**
其所有询问均满足子任务 1 的限制，且后两组询问同时满足子任务 3 的限制。
特别的，在第三组询问的限制下，不存在好的有序非负整数对，因此答案为 $0$。
**【样例 #3 解释】**
其所有询问均满足子任务 2 的限制。
**【样例 #4 解释】**
其所有询问均满足子任务 4 的限制。
特别的，在第四、五组询问的限制下，不存在好的有序非负整数对，因此答案为 $0$。
**【数据范围】**
**本题采用捆绑测试。**
对于 $100\%$ 的数据：
- $1 \le T \le 3 \times 10^5$；
- $0 \le A, B < 2^{60}$；
- $5 \le M \le 1.1 \times 10^9$；
- $M$ 为质数。
具体部分分分配如下：
|Subtask 编号|数据范围|分值|
|:--------:|:--------:|:--------:|
|1|$T \le 200, 0 \le A, B \le 8 \times 10^5$|$15$|
|2|对于每组询问，好的数对个数不超过 $1000$ 个|$25$|
|3|$B = 0$|$25$|
|4|无特殊限制|$35$|