#3#5MLE

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

#define ll long long
ll a[110] = {0};
int check[110] = {0};
ll ans = 0ll;
int p = 1;

void dfs(int now, int check[110], int q){
    if(now == 1){
        ans++;
        return;
    }
    for(int i = p; i <= q; i++){
        if(now % a[check[i]] == 0){
            p = i;
            now /= a[check[i]];
            dfs(now, check, q);
            now *= a[check[i]];
        }
    }
}

int main(){
    int t = 0;
    cin>>t;
    a[0] = 1;
    a[1] = 1;
    for(int i = 2; i <= 87; i++){
        a[i] = a[i - 1] + a[i - 2];
    }
    while(t--){
        memset(check, 0, sizeof(check));
        ans = 0ll;
        p = 1;
        int n = 0;
        cin>>n;
        int q = 0;
        for(int i = 2; i < 87; i++){
            if(n % a[i] == 0) check[++q] = i;
            if(a[i] > n) break;
        }
        dfs(n, check, q);
        cout<<ans;
        printf("\n");
    }
    return 0;
}