Liczby Fibonacciego

#include<cstdio>
int m;
 
struct matrix
{
	long long a, b, c, d;
	matrix(int aa = 0, int bb = 1, int cc = 1, int dd = 0) {a = aa; b = bb; c = cc; d = dd;}
	matrix operator* (matrix x)
	{
		matrix w;
		w.a = ((a * x.a) % m + (b * x.c) % m) % m;
		w.b = ((a * x.b) % m + (b * x.d) % m) % m;
		w.c = ((c * x.a) % m + (d * x.c) % m) % m;
		w.d = ((c * x.b) % m + (d * x.d) % m) % m;
		return w;
	}
};
 
matrix power(matrix x, int n)
{
	if(n == 0) return matrix();
	matrix y = power(x, n/2);
	y = y * y;
	if(n % 2) return y * x;
	return y;
}
 
void test()
{
	int n;
	scanf("%d%d", &n, &m);
	matrix x(0,1,1,1);
	x = power(x, n);
	printf("%d\n", x.c);
}
int main()
{
	int t;
	for(scanf("%d", &t); t--; test());
}