Banda lu' Bahoi

Pe măsură ce se apropie Crăciunul, lucrurile devin foarte aglomerate la Polul Nord. Elfii, forța principală de muncă a Moșului, dispun de o bandă rulantă de lungime infinită, împărțită în chenare. Inițial, pe bandă se află doar un cadou, situat pe poziția $1$. Pentru a determina numărul de cadouri care vor fi în chenarul $k$, Bahoi șeful executiv al Moșului va deplasa banda cu o poziție la dreapta, adunând numărul de cadouri de pe poziția $k-1$ (după deplasare) la numărul de cadouri de pe poziția $k-1$ (înainte de deplasare).

Cu alte cuvinte, dacă $q_k$ este numărul de cadouri din chenarul $k$, atunci $q_k = q_{k-1} + q_{k-2}$, pentru oricare $k \geq 2$.

Cerință

Din cauza haosului de la Polul Nord, șeful executiv Bahoi dorește să verifice dacă a calculat corect numărul de cadouri din fiecare chenar. Astfel, el își pune $Q$ întrebări, fiecare întrebare fiind de forma: care este numărul total de cadouri din chenarele cuprinse între $l$ și $r$? Datorită programului său încărcat, el consideră suficient să afle restul numărului total de cadouri la împărțirea cu $M$.

Date de intrare

Pe prima linie se găsește numărul $Q$ și pe următoarele $Q$ linii câte 3 numere, reprezentând $l$, $r$ și $M$.

Date de ieșire

Pe linia $i$ a output-ului se va găsi răspunsul la întrebarea cu numărul $i$.

Restricții și precizări

• Vom considera că pe poziția $0$ nu se află niciun cadou.
• $1 \leq Q \leq 200 \ 000$
• $0 \leq l \leq r \leq 10^{18}$
• $1 \leq M \leq 2 \cdot 10^9$
• Pentru $40$ de puncte, $r \leq 200 \ 000$ și $M = 10^9 + 7$.

Exemplu

stdin

3
0 5 1000
1 3 1000000007
8 8 18

stdout

12
4
3