#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const ll inf=1e18; int t,p; bool chk(int x){ for(int i=2;i*i<=x;++i)if(!(x%i))return 0; return 1; }vector<int>v; map<vector<int>,int>mp; inline int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%p; a=a*1ll*a%p;b>>=1; }return res; } void dfs(int x,ll s,vector<int>&ve){ map<int,int>f;f[1]=1; up(i,0,(int)ve.size()-1){ map<int,int>g; for(auto [x,y]:f){ g[x*(ve[i]+1)]+=y; g[x*ve[i]]-=2*y; g[x*(ve[i]-1)]+=y; } f.swap(g); } int sum=0; for(auto [x,y]:f)sum=(sum+((y%p)+p)%p*1llu*qp(2,x))%p; mp[ve]=sum; for(int i=1;;++i){ if(ve.size()&&i>ve.back())break; if(s>inf/v[x])break; s*=v[x];ve.eb(i);dfs(x+1,s,ve);ve.pop_back(); } } void init(){ up(i,2,100)if(chk(i))v.eb(i); vector<int>v;dfs(0,1,v); } void slv(){ t=read(),p=read();init(); mp[{}]=1; while(t--){ ll n=read(); vector<int>ve; for(int x:v)if(!(n%x)){ int c=0;while(!(n%x))n/=x,c++; ve.eb(c); } sort(ve.begin(),ve.end(),greater<int>()); printf("%d\n",mp[ve]); } } int main(){ //freopen("pain.in","r",stdin),freopen("pain.out","w",stdout); slv(); return 0; }