//#define DBG
//
//  main.cpp
//  FMINoStress
//
//  Created by Laur Ion on 11/15/13.
//  Copyright (c) 2013 Laur Ion. All rights reserved.

#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

//long long n;
int t, MOD;
long long N, i, mod;
long long MAT[3][3];



ifstream fin("melodii.in");
ofstream fout("melodii.out");

//void inmultire(long long a[][3], long long b[][3]){
//    long long c[3][3] = {0};
//    int i, j, k;
//    for(i = 0; i < 2; ++i)
//        for(j = 0; j < 2; ++j)
//            for(k = 0; k < 2; ++k)
//                c[i][j] = (c[i][j] + ((long long)a[i][k] * b[k][j]%MOD)) % MOD;
//    memcpy(a, c, sizeof(c));
//}
//void solve2(){
//    long long a[3][3];
//    a[0][0] = 0; a[0][1] = 1; a[1][0] = 1; a[1][1] = 1;
//    long long sol[3][3];
//    sol[0][0] = sol[1][1] = 1;
//    //n --;
//    for(; n; (n >>=1) ){
//        if(n & 1)
//            inmultire(sol, a);
//        inmultire(a, a);
//    }
//    fout<<sol[1][1]<<'\n';
//}
inline void mult(long long A[][3], long long B[][3], long long C[][3]) {
    long long i, j, k;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            for (k = 0; k < 2; k++)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % mod;
    
}

inline void solve(long long P, long long M[][3]) {
    long long C[3][3], AUX[3][3], i;
    
    memcpy(C, MAT, sizeof(MAT));
    M[0][0] = M[1][1] = 1;
    
    for (i = 0; (1 << i) <= P; i++) {
        if (P & (1 << i)) {
            memset(AUX, 0, sizeof(AUX));
            mult(M, C, AUX);
            memcpy(M, AUX, sizeof(AUX));
        }
        
        memset(AUX, 0, sizeof(AUX));
        mult(C, C, AUX);
        memcpy(C, AUX, sizeof(C));
    }
}

int main(){
    
    
    fin>>t>>mod;
//    MOD = 666013;
    while(t){
        --t;
        fin>>N;
        long long SOL[3][3];
		MAT[0][0] = 0; MAT[0][1] = 1; MAT[1][0] = 1; MAT[1][1] = 1;
        
        solve(N, SOL);
        fout<<SOL[1][1]<<'\n';
    }
    return 0;
}