Вася дуже любить програмувати. А ще він дуже любить наукову фантастику. Якось на канікулах, начитавшись книжок зі своїм другом Петром, Вася вирішив вивести формулу, яка показує зрост ання популяції на Марсі. За прикидками Васі після \textbf{n} років життя планети популяція марсіан повинна складати \textbf{s_\{n \}}марсіан, де \textbf{s_\{n \}}визначається за формулою: \includegraphics{https://static.e-olymp.com/content/ec/ec86af1d8bf3d63cb1a5913a0ec4269d91ebdbe6.jpg} Петро, після того як Вася розповів йому свою теорію, засумніваіся і вирішив обчислити це число на комп`ютері, щоб переконатись у його достовірності. До того ж, Петро недавно прочитав розумну книжку з программування, тому він думає, що це не займе багато часу. Вам пропонуєьтся зробити те ж саме, але без читання розумної книжки. Відмітьте, що для Вашої зручності потрібно вивести \textbf{s_\{n \}}за модулем \textbf{m}. \InputFile Перший рядок містить кількість тестів. Для кожного тесту в окремому рядку міститься вік n планети Марс та модуль m (\textbf{0} < \textbf{n} ≤ \textbf{10^9}, \textbf{0} < \textbf{m} ≤ \textbf{10^9)}. \OutputFile Для кожного тесту вивести очікуване число марсіан після \textbf{n} років життя планети за модулем \textbf{m}.