#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int maxn = 1e2;
int lcy;

struct Matrix {
	int c, r;
	LL a[3][3];
	inline void Clear() {
		c = r = 0;
		memset(a, 0, sizeof(a));
	}
	
	inline Matrix operator *(const Matrix &b) const {
		Matrix Tmp;
		Tmp.Clear();
		Tmp.c = c, Tmp.r = b.r;
		for(int i = 1; i <= c; i++) {
			for(int j = 1; j <= b.r; j++) {
				for(int k = 1; k <= r; k++) {
					Tmp.a[i][j] = (Tmp.a[i][j] + a[i][k] * b.a[k][j]) % lcy;
				}
			}
		}
		return Tmp;
	}
	
	inline void Base(int Num) {
		memset(a, 0, sizeof(a));
		for(int i = 1; i <= Num; i++) a[i][i] = 1;
		c = Num, r = Num;
	}
	
	void Out() {
		for(int i = 1; i <= c; i++) {
			for(int j = 1; j <= r; j++) {
				printf("%lld ", a[i][j]);
			}
			printf("\n");
		}
	}
};

inline Matrix MatrixQuickPow(Matrix Tar, long long Times) {
	Matrix Tmp = Tar;
	Tar.Base(2);
	while(Times) {
		if(Times & 1ll) Tar = Tar * Tmp;
		Times >>= 1;
		Tmp = Tmp * Tmp;
	}
	return Tar;
}

Matrix a1, a2, a3;
long long n, m;

void solve() {
	if(n == 0) {
		printf("0\n");
		return;
	}
	if(n == 1) {
		printf("%d\n", 1 % lcy);
		return;
	}
	if(n == 2) {
		printf("%d\n", 1 % lcy);
		return;
	}
	a1.a[1][1] = 1;
	a1.a[2][1] = 1;
	a1.c = 2, a1.r = 1; 
	a2.a[1][1] = 1;
	a2.a[2][1] = 1;
	a2.a[1][2] = 1;
	a2.a[2][2] = 0;
	a2.c = a2.r = 2;
	a2 = MatrixQuickPow(a2, n - 2);
	a1 = a2 * a1;
	printf("%lld\n", a1.a[1][1]);
} 

int main() {
	freopen("eins.in", "r", stdin);
	freopen("eins.out", "w", stdout);
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++) {
		scanf("%d %d", &n, &lcy);
		solve();
		// if (not (i % 5000)) printf("done");
	}
	return 0;
}