Fiboxor
Description
Consider the following integer sequence $f$:
$f_1 = f_2 = 1$, $f_k = |f_{k-1} - f_{k-2}| \oplus (f_{k - 1} + f_{k - 2})$, for $k \geq 3$.
Now, you are wondering, for $q$ triples of integers ($l, r, M$), what is the sum of all $f_i$, $l \leq i \leq r$, modulo $M$. That is, find $\displaystyle(\sum_{i = l}^rf_i)$ and print it's remainder modulo $M$.
By $|x|$ we denote the absolute value of $x$ and by XOR we denote the bitwise XOR operation.
In the first line of input, you will read one integer $q$ ($1 \leq q \leq 2 \cdot 10^5$).
In the next $q$ lines, you will read three integers $l$, $r$ ($1 \leq l \leq r \leq 10^9$) and $M$ ($10^8 < M < 10^9$, $M$ is prime).
Output $q$ lines, the $i^{th}$ of them representing the answer for the $i^{th}$ triple ($l, r, M$).
Input
In the first line of input, you will read one integer $q$ ($1 \leq q \leq 2 \cdot 10^5$).
In the next $q$ lines, you will read three integers $l$, $r$ ($1 \leq l \leq r \leq 10^9$) and $M$ ($10^8 < M < 10^9$, $M$ is prime).
Output
Output $q$ lines, the $i^{th}$ of them representing the answer for the $i^{th}$ triple ($l, r, M$).
4
1 3 998244353
2 4 998244353
4232324 12345678 998244353
92345678 998244353 998244353
4
5
652671816
367684397
Note
The first four values of $f$ are: $f_1 = 1, f_2 = 1, f_3 = 2, f_4 = 2$.
Thus, the answer for the first question is $1 + 1 + 2 = 4$ and the answer for the second question is $1 + 2 + 2 = 5$.