#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("tritzi.in");
ofstream fout ("tritzi.out");
int T, N, MOD;
typedef int mat[3][3];
void prod(mat A, mat B)
{   mat C;
    memset(C, 0, sizeof C);
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 3; ++j)
            for(int k = 0; k < 3; ++k)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    memcpy(A, C, sizeof C);
}
int solve(int P)
{   mat Rez, T;
    memset(Rez, 0, sizeof Rez);
    memset(T, 0, sizeof T);
    Rez[1][1] = Rez[2][2] = Rez[0][0] = 1;
    T[0][0] = T[0][2] = T[1][1] = T[1][2] = T[2][1] = T[2][2] = T[2][0] = 1;
    for(; P; P >>= 1)
    {   if(P & 1) prod(Rez, T);
        prod(T, T);
    }
    int Sol = 0;
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 3; ++j)
        {   Sol += Rez[i][j];
            if(Sol >= MOD) Sol -= MOD;
        }
    return Sol;
}
int main()
{   for(fin >> T; T; --T)
    {   fin >> N >> MOD;
        fout << solve(N-1) << "\n";
    };
    return 0;
}