E. Fiboxor
time limit per test
1 second
memory limit per test
256 MB
input
standard input
output
standard output

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.

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 \lt M \lt 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$$$).

Example
Input
4
1 3 998244353
2 4 998244353
4232324 12345678 998244353
92345678 998244353 998244353
Output
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$$$.