#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int  main() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    unsigned long long n, maxi = 0;
    long long q, m;
    long long suma = 0;
    cin >> q >> m;
    vector<unsigned long long> v2;
    vector<unsigned long long> v1;
    v2.push_back(0 % m);
    v2.push_back(2 % m);
    v2.push_back(2 % m);
    for (int i = 0; i < q; i++)
    {
        cin >> n;
        maxi = max(maxi, n);
        v1.push_back(n);
    }
    for(unsigned long long i = 3; i <= maxi; i++)
    {
        suma = i - pow(2, 0);
        v2.push_back(v2[suma]);
        for(unsigned long long d = 1; d <= ceil(log(i)); d++)
        {
            suma = i - pow(2, d);
            if(suma <= 0) break;
            v2[i] += v2[suma];
        }
        v2[i] = v2[i] % m;
    }
    for(unsigned long long i = 0; i < q; i++) cout << v2[v1[i]] << "\n";
}