#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <cctype>
using namespace std;

long long MOD;
struct matrix
{
	long long x[2][2];
	matrix mul(matrix &m)
	{
		matrix r;
		for(int i = 0; i < 2; i++)for(int j = 0; j < 2; j++)
		{
			r.x[i][j] = 0;
			for(int k = 0; k < 2; k++)r.x[i][j]+=x[i][k]*m.x[k][j]%MOD;
			r.x[i][j] %= MOD;
		}
		return r;
	}
	long long pow(long long exp)
	{
		matrix a, ans;
		a.x[0][0] = a.x[0][1] = a.x[1][0] = 1;
		a.x[1][1] = 0;
		ans.x[0][0] = ans.x[1][1] = 1;
		ans.x[1][0] = ans.x[0][1] = 0;
		while(exp)
		{
			if(exp & 1)
			{
				ans = ans.mul(a);
			} 
			a = a.mul(a);
			exp >>= 1;
		} 
    	return ans.x[0][1];
	}
};


int main()
{
    freopen("eins.in", "r", stdin);
    freopen("eins.out", "w", stdout);
    int T;
    scanf("%d", &T);
	matrix t;
	while(T--)
	{
        long long n;
		scanf("%lld %lld", &n, &MOD);
	    printf("%lld\n", t.pow(n));
	}
	return 0;
}