RoAlgo Contest #8 | Banda lu' Bahoi

As Christmas approaches, things become very busy at the North Pole. The elves, Santa's main workforce, have an infinitely long conveyor belt divided into slots. Initially, there is only one gift on the conveyor belt, located at position $1$. To determine the number of gifts in slot $k$, Bahoi, Santa's chief executive, will move the conveyor belt one position to the right, adding the number of gifts from position $k-1$ (after the move) to the number of gifts from position $k-1$ (before the move).

In other words, if $q_k$ is the number of gifts in slot $k$, then $q_k = q_{k-1} + q_{k-2}$, for any $k \geq 2$.

Task

Due to the chaos at the North Pole, chief executive Bahoi wants to verify if he has correctly calculated the number of gifts in each slot. Thus, he asks himself $Q$ questions, each question being in the form: what is the total number of gifts in the slots between $l$ and $r$? Due to his busy schedule, he considers it sufficient to find the remainder of the total number of gifts when divided by $M$.

Input data

The first line contains the number $Q$ and the next $Q$ lines contain 3 numbers each, representing $l$, $r$, and $M$.

Output data

On line $i$ of the output, you will find the answer to the question number $i$.

Constraints and clarifications

• We will consider that there are no gifts at position $0$.
• $1 \leq Q \leq 200\,000$
• $0 \leq l \leq r \leq 10^{18}$
• $1 \leq M \leq 2 \cdot 10^9$
• For $40$ points, $r \leq 200\,000$ and $M = 10^9 + 7$.

Example

stdin

3
0 5 1000
1 3 1000000007
8 8 18

stdout

12
4
3

Explanation

For instance, for the first query, the total number of gifts in slots $0$ to $5$ is $12$, and $12 \mod 1000$ is $12$. For the second query, the total number of gifts in slots $1$ to $3$ is $4$, and $4 \mod 1000000007$ is $4$. For the third query, the number of gifts in slot $8$ is $21$, and $21 \mod 18$ is $3$.