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 JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.math.*;


public class d {
    String _token() throws IOException {
        while (in.ready() && !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        if (st.hasMoreTokens())
            return st.nextToken();
        return "";
    }
    
    
    int N = 91;
    long fib[] = new long [N+1]; 
    
    void do_solve() throws NumberFormatException, IOException {
        long n = _long();
        ArrayList<Integer> a = new ArrayList<Integer>(0);
        for(int mx = N-1; mx>0; mx--) {
            if (n>=fib[mx]) {
                n-=fib[mx];
                a.add(mx);
            }
        }
        a.add(0);
        int [] b = new int[a.size()];
        for(int i=0;i<a.size();i++) {
            b[i] = a.get(a.size() - i-1);
        }
        long ans[][] = new long [2][b.length];
        ans[0][0] = 1;
        ans[1][0] = 0;
        for(int i=1;i<b.length;i++) {
//          deb(b[i]);
            ans[0][i] = ans[0][i-1] + ans[1][i-1];
            ans[1][i] = ans[0][i-1] * ((b[i] - b[i-1] - 1)/2) + 
                        ans[1][i-1] * (((b[i] - b[i-1] - (i==1?1:0))/2));
        }
        
        out.println(ans[0][b.length-1] + ans[1][b.length-1]);
    }
    void mainProgram() throws NumberFormatException, IOException {
        
//      test("d.in");
        
        init(false, "d");
        boolean multy = true;

        fib[0] = 1;
        fib[1] = 1;
        for(int i=2;i<N;i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }
        if (!multy) {
            while (in.ready() || st.hasMoreTokens()) {
                do_solve();
            }
        } else {
            for (int T = _int(); T > 0; --T) {
                do_solve();
            }
        }
        out.close();
    }

    int rand(double x) {
        return (int) (Math.random() * x);
    }

    void test(String name) throws IOException {
        out = new PrintWriter(new File(name));
        int n = (int)100000;
        out.println(n);
        for(int i=0;i<n;i++) {
//          out.println(rand(1e9)*(long)rand(1e9));
            out.println(i+1);
        }
        out.close();
    }

    void init(boolean FILE, String name) throws NumberFormatException,
            IOException {
        Locale.setDefault(Locale.US);
        if (FILE) {
            in = new BufferedReader(new FileReader(name + ".in"));
            out = new PrintWriter(name + ".out");
        } else {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }
        st = new StringTokenizer("");
    }

    public static void main(String[] args) throws NumberFormatException,
            IOException {
        long T = System.currentTimeMillis();
        new d().mainProgram();
        System.err.println("Time of working: "
                + (System.currentTimeMillis() - T) + " ms");
    }

    void deb(String s) {
        System.err.println(s);
    }

    void deb(Object a) {
        System.err.println(a.toString());
    }

    BigInteger add(BigInteger A, BigInteger B) {
        return A.add(B);
    }

    BigInteger mult(BigInteger A, BigInteger B) {
        return A.multiply(B);
    }

    BigInteger sub(BigInteger A, BigInteger B) {
        return A.subtract(B);
    }

    BigInteger div(BigInteger A, BigInteger B) {
        return A.divide(B);
    }

    BigInteger mi(BigInteger A) {
        return (BigInteger.ZERO).subtract(A);
    }

    BigInteger sq(BigInteger A) {
        return A.multiply(A);
    }

    BigInteger val(long a) {
        return BigInteger.valueOf(a);
    }

    int cmp(BigInteger a, BigInteger b) {
        return a.compareTo(b);
    }

    BufferedReader in;
    StringTokenizer st;
    PrintWriter out;

    int _int() throws NumberFormatException, IOException {
        return Integer.parseInt(_token());
    }

    long _long() throws NumberFormatException, IOException {
        return Long.parseLong(_token());
    }

    double _double() throws NumberFormatException, IOException {
        return Double.parseDouble(_token());
    }

    int gcd(int a, int b) {
        if (a < 0)
            a = -a;
        if (b < 0)
            b = -b;
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    long gcd(long a, long b) {
        if (a < 0)
            a = -a;
        if (b < 0)
            b = -b;
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    BigInteger gcd(BigInteger a, BigInteger b) {
        if (cmp(a, val(0)) < 0)
            a = mi(a);
        if (cmp(b, val(0)) < 0)
            b = mi(b);
        return a.gcd(b);
    }
}