#include <cstdio>#include <algorithm>#include <iostream>#include <string.h>typedef long long LL;using namespace std;LL mod;struct Matrix{    LL m[4][4];};Matrix Mul(Matrix a, Matrix b){    Matrix ans;    for (LL i = 0; i < 2; i++){        for (LL j = 0; j < 2; j++){            ans.m[i][j] = 0;            for (LL k = 0; k < 2; k++)                ans.m[i][j] += a.m[i][k] * b.m[k][j], ans.m[i][j] = (ans.m[i][j] + mod) % mod;        }    }    return ans;}Matrix quick(Matrix a, LL b){    Matrix ans;    for (LL i = 0; i < 2; i++)    for (LL j = 0; j < 2; j++)        ans.m[i][j] = (i == j);    Matrix c;    c = Mul(a, a);    while (b){        if (b & 1) ans = Mul(a, ans);        a = Mul(a, a);        b >>= 1;    }    return ans;}Matrix init(){    Matrix ans;    ans.m[0][0] = 3; ans.m[0][1] = -1;    ans.m[1][0] = 1; ans.m[1][1] = 0;    return ans;}int main(){    LL T;    LL n;    cin >> T;    while (T--){        cin >> n >> mod;        if (n == 0){            cout << 0 << endl; continue;        }        if (n == 1){            cout << 1 << endl; continue;        }        Matrix ans = init();        ans = quick(ans, n - 1);        cout << ans.m[0][0] << endl;    }    return 0;}