Problem: Fibonacci numbers have the following form:

F1 = 1,  F2 = 2,  Fi = Fi - 1 + Fi - 2, i > 2.

Let's consider some non-empty set S = {s1, s2, ..., sk}, consisting of different Fibonacci numbers. Let's find the sum of values of this set's elements:

<image>

Let's call the set S a number n's decomposition into Fibonacci sum. 

It's easy to see that several numbers have several decompositions into Fibonacci sum. For example, for 13 we have 13, 5 + 8, 2 + 3 + 8 — three decompositions, and for 16: 3 + 13, 1 + 2 + 13, 3 + 5 + 8, 1 + 2 + 5 + 8 — four decompositions.

By the given number n determine the number of its possible different decompositions into Fibonacci sum.

Input

The first line contains an integer t — the number of tests (1 ≤ t ≤ 105). Each of the following t lines contains one test.

Each test is an integer n (1 ≤ n ≤ 1018).

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

Output

For each input data test print a single number on a single line — the answer to the problem.

Examples

Input

2
13
16


Output

3
4

Note

Two decompositions are different if there exists a number that is contained in the first decomposition, but is not contained in the second one. Decompositions that differ only in the order of summands are considered equal.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-8;
struct pt {
  long double x, y;
  pt() {}
  pt(long double _x, long double _y) : x(_x), y(_y) {}
  pt operator+(const pt &p) const { return pt(x + p.x, y + p.y); }
  pt operator-(const pt &p) const { return pt(x - p.x, y - p.y); }
  pt operator*(long double c) const { return pt(x * c, y * c); }
  pt operator/(long double c) const { return pt(x / c, y / c); }
  void operator+=(const pt &p) {
    x += p.x;
    y += p.y;
  };
  void operator-=(const pt &p) {
    x -= p.x;
    y -= p.y;
  };
  void operator*=(long double c) {
    x *= c;
    y *= c;
  };
  void operator/=(long double c) {
    x /= c;
    y /= c;
  };
  long double operator/(const pt &p) const { return (x * p.y - y * p.x); }
  long double operator*(const pt &p) const { return (x * p.x + y * p.y); }
  long double length() { return sqrtl(x * x + y * y); }
  long double angle() { return atan2(y, x); }
};
struct treap {
  int key, p, cnt;
  treap *l, *r;
  treap(int _key)
      : key(_key),
        p(((RAND_MAX < 1000000000) ? (rand() * rand()) : (rand()))),
        cnt(1),
        l(NULL),
        r(NULL) {}
};
int getcnt(treap *t) {
  if (t) return t->cnt;
  return 0;
}
treap *upd(treap *t) {
  if (!t) return t;
  t->cnt = 1 + getcnt(t->l) + getcnt(t->r);
}
void split(treap *t, int key, treap *&l, treap *&r) {
  if (!t) return void(l = r = NULL);
  if (t->key < key)
    split(t->l, key, l, t->l), r = t;
  else
    split(t->r, key, t->r, r), l = t;
  upd(t);
}
treap *merge(treap *l, treap *r) {
  if (!l || !r) return max(l, r);
  if (l->p > r->p) {
    l->r = merge(l->r, r);
    return upd(l);
  } else {
    r->l = merge(l, r->l);
    return upd(r);
  }
}
struct rmq {
  int l, r, MaxInd;
  int Max, Add;
  rmq *L, *R;
  rmq(int b, int e) {
    l = b;
    r = e;
    MaxInd = l;
    Max = Add = 0;
    if (b != e) {
      L = new rmq(b, (b + e) / 2);
      R = new rmq((b + e) / 2 + 1, e);
    }
  }
  void SET(int i, int x) {
    if (l == r)
      Max = x;
    else {
      if (i <= L->r)
        L->SET(i, x);
      else
        R->SET(i, x);
      Max = max(L->Max + L->Add, R->Max + R->Add);
      if (Max == L->Max + L->Add)
        MaxInd = L->MaxInd;
      else
        MaxInd = R->MaxInd;
    }
  }
  void ADD(int b, int e, int x) {
    if (b > r || e < l) return;
    if (b <= l && e >= r)
      Add += x;
    else {
      L->ADD(b, e, x);
      R->ADD(b, e, x);
      Max = max(L->Max + L->Add, R->Max + R->Add);
      if (Max == L->Max + L->Add)
        MaxInd = L->MaxInd;
      else
        MaxInd = R->MaxInd;
    }
  }
  int MAX(int b, int e) {
    if (b > r || e < l) return -1000000000;
    if (b <= l && e >= r)
      return Max + Add;
    else {
      return max(L->MAX(b, e), R->MAX(b, e)) + Add;
    }
  }
  pair<int, int> MAX_IND(int b, int e) {
    if (b > r || e < l) return make_pair(-1000000000, -1000000000);
    if (b <= l && e >= r)
      return make_pair(Max + Add, MaxInd);
    else {
      pair<int, int> ans = max(L->MAX_IND(b, e), R->MAX_IND(b, e));
      ans.first += Add;
      return ans;
    }
  }
};
long long power(long long x, long long a, long long p) {
  if (a == 0) return 1;
  if (a % 2 == 0) {
    long long ans = power(x, a / 2, p);
    return (ans * ans) % p;
  } else
    return (power(x, a - 1, p) * x) % p;
}
long long F[1000000];
int mind;
int main() {
  F[0] = 1;
  F[1] = 2;
  for (int i = 2; i < 1000000; ++i) {
    F[i] = F[i - 1] + F[i - 2];
    if (F[i] > 1000000000000000000LL) {
      mind = i - 1;
      break;
    }
  }
  int test;
  long long n;
  cin >> test;
  vector<long long> a(1000), b(1000);
  long long d[1000][2];
  for (int t = 0; t < test; ++t) {
    scanf("%I64d", &n);
    a.resize(0);
    b.resize(0);
    int ind = mind;
    while (n) {
      if (n >= F[ind]) n -= F[ind], a.push_back(ind), b.push_back(0);
      ind--;
    }
    a.push_back(-1);
    b.push_back(0);
    long long res = 1;
    for (size_t i = 0; i < a.size() - 1; ++i) {
      if (a[i + 1] > 1 && (a[i] - a[i + 1] - 1) % 2 == 1) b[i] = 1;
      a[i] = (a[i] - a[i + 1] - 1) / 2 + 1;
    }
    a.resize(a.size() - 1);
    b.resize(b.size() - 1);
    for (size_t i = 0; i <= a.size(); ++i) d[i][0] = d[i][1] = 0;
    d[0][0] = a[0] + b[0];
    d[0][1] = a[0];
    for (size_t i = 1; i < a.size(); ++i) {
      d[i][0] = max(0LL, (a[i] - 1 + b[i])) * d[i - 1][0] + d[i - 1][1];
      d[i][1] = max(0LL, (a[i] - 1)) * d[i - 1][0] + d[i - 1][1];
    }
    res = d[a.size() - 1][0];
    printf("%I64d\n", res);
  }
  return 0;
}