#include "iostream"

#include "cstdio"

using namespace std;

#define LL long long

#define N 100020

int a[N],b[N];

void init()

{

    a[]=;a[]=a[]=;

    b[]=;b[]=b[]=;

    for(int i=;i<N;i++){

        if(i%)

            a[i]=a[i/]+a[i/+];

        else

            a[i]=a[i/];

        b[i]=max(b[i-],a[i]);

    }

}

int main(){

   //freopen("in.txt","r",stdin);

    init();

    int t,n;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        printf("%d\n",b[n]);

    }

    return ;

}