Masala C

\(A_1=1\)

\(A_2=1\)

\(A_i=|A_{i-1}-A_{i-2}| \oplus(A_{i-1}+A_{i-2})\) agar \(i>2\)

Bu yerda \(\oplus\) bitwise xor amalini anglatadi.

Shu shartlar asosida qurilgan \(A\) ketma-ketlik mavjud.

Sizning vazifangiz berilgan \(L\), \(R\) va \(M\) sonlari uchun \((A_L+A_{L+1}+A_{L+2}+...+A_R) \ \ mod \ \ M\) ning qiymatini, ya'ni ketma-ketlikning \(L\) - tartibdan \(R\) - tartibgacha bo'lgan elementlari yig'indisini \(M\) ga bo'lgandagi qoldiqni aniqlashdan iborat.

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 2 \times 10^5)\) testlar soni kiritiladi.

Keyingi \(T\) ta satrda uchtadan butun son, \(L(1 \le L \le 10^9)\), \(R(L \le R \le 10^9)\) va \(M(1\le M \le 10^9)\) sonlari kiritiladi.

Kiritilgan \(M\) tub son ekanligi kafolatlanadi.

Har bir test uchun alohida qatorda bitta butun son, masala shartida so'ralgan qiymatni chop eting.