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

#define int long long

vector<int>f;

int solve(int x){
	if(x==1||x==2){
		return 1;
	}
	int ans=0;
	for(int i:f){
		if(i==1){
			continue;
		}
		if(x%i){
			continue;
		}
		ans+=solve(x/i);
	}
	return ans;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	f.push_back(1);
	f.push_back(2);
	for(int i=0;i<30;i++){
		f.push_back(*--f.end()+*----f.end());
	}
	int T;
	cin>>T;
	while(T--){
		int M;
		cin>>M;
		cout<<solve(M)<<'\n';
	}
	return 0;
}