Оцінка
Вася дуже любить програмувати. А ще він дуже любить наукову фантастику. Якось на канікулах, начитавшись книжок зі своїм другом Петром, Вася вирішив вивести формулу, яка показує зрост ання популяції на Марсі. За прикидками Васі після n років життя планети популяція марсіан повинна складати s_{n }марсіан, де s_{n }визначається за формулою:
Петро, після того як Вася розповів йому свою теорію, засумніваіся і вирішив обчислити це число на комп'ютері, щоб переконатись у його достовірності. До того ж, Петро недавно прочитав розумну книжку з программування, тому він думає, що це не займе багато часу.
Вам пропонуєьтся зробити те ж саме, але без читання розумної книжки. Відмітьте, що для Вашої зручності потрібно вивести s_{n }за модулем m.
Вхідні дані
Перший рядок містить кількість тестів. Для кожного тесту в окремому рядку міститься вік n планети Марс та модуль m (0 < n ≤ 10^9, 0 < m ≤ 10^9).
Вихідні дані
Для кожного тесту вивести очікуване число марсіан після n років життя планети за модулем m.