#include<bits/stdc++.h>
using namespace std;

#define int long long

vector<int>f,v,F;

map<int,int>m;

void solve(int x,int i,int c,int d){
	if(x>1000000000){
		return;
	}
	if(d){
		int ans=1;
		v.push_back(c);
		int dd=d;
		for(int j:v){
			ans*=F[dd]/F[j]/F[dd-j];
			dd-=j;
		}
		m[x]+=ans;
		v.pop_back();
	}
	for(int j=i;j<f.size();j++){
		if(j==i){
			solve(x*f[j],j,c+1,d+1);
		}
		else{
			v.push_back(c);
			solve(x*f[j],j,1,d+1);
			v.pop_back();
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	f.push_back(1);
	f.push_back(2);
	F.push_back(1);
	for(int i=0;i<42;i++){
		f.push_back(*--f.end()+*----f.end());
		F.push_back(F.back()*(i+1));
	}
	cout<<f.back()<<endl;
	solve(1,1,0,0);
	int T;
	cin>>T;
	while(T--){
		int M;
		cin>>M;
		if(M==1){
			cout<<1<<'\n';
			continue;
		}
		cout<<m[M]<<'\n';
	}
	return 0;
}