// Arup Guha
// 9/7/2013
// Solution to UCF JV Practice Problem E: Fibonacci Sum

import java.util.*;

public class e {

	// Note: F(44) is a bit more than 1 billion...
	final public static int NUMFIBS = 45;
	public static int[] fibs;

	public static void main(String[] args) {

		// Pre-compute fibs.
		fibs = new int[NUMFIBS];
		fibs[0] = 1;
		fibs[1] = 1;
		for (int i=2; i<NUMFIBS; i++)
			fibs[i] = fibs[i-1] + fibs[i-2];

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process each case.
		for (int loop=0; loop<numCases; loop++) {
			int n = stdin.nextInt();
			System.out.println(solve(n));
		}
	}

	public static int solve(int n) {

		// Just do a greedy, subtracting out the biggest fibonacci number possible.
		int cnt = 0, i = NUMFIBS-1;
		while (n != 0) {
			if (fibs[i] <= n) {
				cnt++;
				n -= fibs[i];
			}
			i--;
		}
		return cnt;
	}
}