11.29T3

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,fib[100],ans;bool vis[100000000];
void dfs(int x2,int x3,int x8,int x144) {
	if(vis[x2*1000000+x3*10000+x8*100+x144]) return;
	ans++;vis[x2*10000000+x3*10000+x8*100+x144]=1;
	if(x2>=3) dfs(x2-3,x3,x8+1,x144);
	if(x2>=1&&x3>=2&&x8>=1) dfs(x2-1,x3-2,x8-1,x144+1);
}
void work() {
	cin>>n;ans=0;
	int s2=0,s3=0;
	for(int i=85;i>=3;i--) {
		if(fib[i]==8||fib[i]==144) continue;
		while(n%fib[i]==0) n/=fib[i];
	}
	while(n%2==0) n/=2,s2++;
	while(n%3==0) n/=3,s3++;
	if(n>1){cout<<"0\n";return;}
	dfs(s2,s3,0,0);cout<<ans<<"\n";
}
signed main() {
	freopen("fibonacci.in","r",stdin);
	freopen("fibonacci.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);
	for(int a=1,b=2,i=1;b<=1e18;i++) {
		fib[i]=b;int t=a+b;a=b;b=t;
	}int T;cin>>T;while(T--) work();
}