#include <fstream>
#include <cmath>
using namespace std;
int n, p;
class Matrix {
public:
    void Init() {
        e_[0][0]=1;
        e_[0][1]=1;
        e_[1][0]=1;
        e_[1][1]=0;
    }
    void Unit(){
        e_[0][0]=1;
        e_[0][1]=0;
        e_[1][0]=0;
        e_[1][1]=1;
    }
public:
    int Get() const {
        return e_[0][1];
    }
    friend Matrix operator*(const Matrix& A, const Matrix& B){
        Matrix AB;
        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < 2; ++j){
                AB.e_[i][j] = 0;
                for(int k = 0; k < 2; ++k)
                    AB.e_[i][j] += A.e_[i][k] * B.e_[k][j];
            }
        for(int i = 0; i < 2; ++i) for(int j = 0; j < 2; ++j)
            AB.e_[i][j] %= p;
        return AB;
    }
private:
    __int64 e_[2][2];
};
int qpow(Matrix& AB, int n){
    #define Bit(n) 1<<n
    Matrix t;
    t.Init();
    for(int i = 0; Bit(i) <= n; ++i){
        if(Bit(i) & n) AB = AB * t;
        t = t * t;
    }
    return AB.Get();
}
int main(){
    fstream in("eins.in", ios::in), out("eins.out", ios::out);
    in >> n;
    for(int i = 0; i < n; ++i){
        int n2;
        in >> n2 >> p;
        Matrix m;
        m.Unit();
        out << qpow(m, n2) << endl;
    }
    return 0;
}