Qiymətləndirmə
Vasya proqramlaşdırmanı çox sevir və elmi fantastikaya da marağı böyükdür. Bir dəfə tətil zamanı, dostu Pyotr ilə kitab oxuyarkən, Vasya Marsda əhalinin artımını göstərən bir düstur yaratmağa qərar verdi. Onun hesablamalarına görə, planetin n ilindən sonra marslıların əhalisi s_{n} marslı olmalıdır. Bu əhali sayı aşağıdakı düsturla müəyyən edilir:
Vasya nəzəriyyəsini Pyotr ilə paylaşdıqdan sonra, Pyotr bu rəqəmlərin doğruluğunu yoxlamaq üçün kompüterdə hesablamalar aparmağa qərar verdi. O, yaxınlarda proqramlaşdırma haqqında ağıllı bir kitab oxuduğu üçün bunun çox vaxt almayacağını düşünür.
Sizdən də eyni hesablamaları aparmağınız xahiş olunur, amma ağıllı kitab oxumadan. Qeyd edək ki, sizin rahatlığınız üçün s_{n} modulu m ilə çıxarılmalıdır.
Giriş verilənləri
Birinci sətir testlərin sayını göstərir. Hər bir test üçün ayrıca sətirdə Mars planetinin yaşı n və modul m (0 < n ≤ 10^9, 0 < m ≤ 10^9) verilir.
Çıxış verilənləri
Hər bir test üçün planetin n ilindən sonra gözlənilən marslıların sayını modul m ilə çıxarın.