RCPC Simulare 2023 day 2 | E. Fiboxor

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 $\oplus$ we denote the bitwise XOR operation.

Input data

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 data

Output $q$ lines, the $i^{th}$ of them representing the answer for the $i^{th}$ triple ($l, r, M$).

Example

stdin

4
1 3 998244353
2 4 998244353
4232324 12345678 998244353
92345678 998244353 998244353

stdout

4
5
652671816
367684397

Explanation

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$.