#include<iostream>
#define ll long long
using namespace std;
ll fib[100];
int init(){
	int ans=0;
	fib[1]=1,fib[2]=1;
	for(int i=3;fib[i-1]<1e18;i++){
		fib[i]=fib[i-1]+fib[i-2];
		ans++;
	}
	return ans;
}
ll solve(int n,int d){
	if(n==1) return 1;
	if(d<=2) return 0;
	while(fib[d]>n){
		d--;
	}
	ll ans=0;
	if(fib[d]!=0&&n%fib[d]==0){
		ans+=solve(n/fib[d],d);
	}
	return ans+solve(n,d-1);
}
int main(){
	int f=init();
	int t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		cout<<solve(n,86)<<endl;
	}
	return 0;
}