ADV04I

ADV04I


#include<iostream>
#include<cstdio>
#include<vector>
#include<list>
#include<string>
#include<map>
#include<algorithm>
#include<complex>
#define fn(i,j,n) for(int i=j;i<n;i++)
#define rn(i,n) fn(i,0,n)
using namespace std;
int main()
{
long long int a,b,i;
a = b = 1;
long long int c;
long long int arr[76];
arr[0]=1;
fn(i,1,75)
    {
    c = a+b;
    arr[i] = c    ;
    a = b;
    b = c;
    }
vector<long long int> fib(arr,arr+76);
int t;
cin>>t;
long long int number;
while(t--)
{
    cin>>number;
    long long int res = 0,num1,num2;
    vector<long long int>::iterator it,kn;
    it = lower_bound(fib.begin(),fib.end(),number);
    kn = it;
    if(*it == number)
        it++;
    num1=*it;
    it--;
    num2=*it;
   
    res = res + num1;
    number = number - num2;
   
    while(number>0)
    {
        it = lower_bound(fib.begin(),kn,number);
        kn=it;
        if(*it==number)
            it++;
        num1=*it;
        it--;
        num2=*it;
        res = res + num1;
        number = number - num2;
       
    }   
    cout<<res<<endl;
}   
return 0;
}