8842번 - Paski 다국어

문제

Hektor posiada długi prostokątny pasek papieru, podzielony na 1073741824 równych prostokątnych sektorów, ułożonych jeden po drugim. Sektory te są ponumerowane kolejnymi liczbami naturalnymi, poczynając od 1. Hektor zamierza pociąć swój pasek na drobniejsze kawałki. Jego cięcia zawsze są perfekcyjne - przechodzą dokładnie przez środek ciętego paska. Ponadto nigdy nie połowi on pasków długości nie większej niż jeden sektor.

Po skończonych cięciach Hektor zauważył, że powstałe paski pozwalają na dokładne odtworzenie (poprzez położenie obok siebie kilku z nich) paska liczb z przedziału [a,b]. Zastanawia się teraz, ile różnych odtworzeń tego przedziału mógłby uzyskać, gdyby wykonywał inne cięcia. Pomóż mu rozwiązać ten problem.

입력

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z (1 <= Z <= 10).

W każdej z kolejnych Z linii znajdują się trzy liczby całkowite: a, b, m (1 <= a <= b <= 1073741824, 1 <= m <= 1000000).

출력

Dla każdego zestawu testowego należy wypisać jedną liczbę całkowitą - resztę z dzielenia przez m ilości różnych możliwych pocięć przedziału [a,b], możliwych do uzyskania przez Hektora.

제한

힌트

Jest tylko jeden sposób, żeby odtworzyć dokładnie liczby z przedziału [2,2] - trzeba posiadać pasek symbolizujący pojedynczy sektor 2.

W drugim teście mamy odtworzyć liczby z przedziału [3,4], co możemy zrobić na dwa sposoby - albo za pomocą jednego paska pokrywającego cały przedział [3,4], albo za pomocą dwóch pasków: [3,3] oraz [4,4].

W trzecim teście przedział [1,3] można odtworzyć również na dwa sposoby: albo przedziałami [1,1], [2,2], [3,3], albo tylko dwoma przedziałami: [1,2], [3,3].