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

#define int long long

vector<int>f,v,F;

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

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));
	}
	int T;
	cin>>T;
	while(T--){
		int M;
		cin>>M;
		cout<<solve(M,1,0,0)<<'\n';
	}
	return 0;
}