#include <fstream>
using namespace std;
ifstream fin("tritzi.in");
ofstream fout("tritzi.out");


int tetse, n, p, i, j, mat[4][4], p[4][4], mod;

void initializare(int a[4][4], ok){
        /// 1 0 1
        /// 0 1 1
        /// 1 1 1
        if(ok==1){
            a[1][1]=1;
            a[1][2]=0;
            a[1][3]=1;
            a[2][1]=0;
            a[2][2]=1;
            a[2][3]=1;
            a[3][1]=1;
            a[3][2]=1;
            a[3][3]=1;
        }
        /// 1 0 0
        /// 0 1 0
        /// 0 0 1
        if(ok==2){
            a[1][1]=1;
            a[1][2]=0;
            a[1][3]=0;
            a[2][1]=0;
            a[2][2]=1;
            a[2][3]=0;
            a[3][1]=0;
            a[3][2]=0;
            a[3][3]=1;
        }
}

void inmultire(int a[4][4], int b[4][4], int rez[4][4]){
    for(int i=1; i<=3; i++){
        for(int j=1; j<=3; j++){
            rez[i][j]=0;
            for(int k=1; k<=3; k++){
                rez[i][j]+=a[i][k]*b[k][j];
                rez[i][j]%=mod;
            }
        }
    }
}



int main(){
    fin>>teste;
    for(; teste; teste--){
        fin>>n>>mod;
        initializare(mat);

    }
}