package main

import (
	"bufio"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	if !scanner.Scan() {
		return
	}
	t, _ := strconv.Atoi(scanner.Text())

	fib := make([]int64, 90)
	fib[1] = 1
	fib[2] = 2
	for i := 3; i < 90; i++ {
		fib[i] = fib[i-1] + fib[i-2]
	}

	for i := 0; i < t; i++ {
		scanner.Scan()
		n, _ := strconv.ParseInt(scanner.Text(), 10, 64)

		var p []int
		for j := 89; j >= 1; j-- {
			if n >= fib[j] {
				n -= fib[j]
				p = append(p, j)
			}
		}

		for l, r := 0, len(p)-1; l < r; l, r = l+1, r-1 {
			p[l], p[r] = p[r], p[l]
		}

		dp0, dp1 := int64(1), int64(0)
		prev := 0

		for _, x := range p {
			d := x - prev
			newDp0 := dp0 + dp1
			newDp1 := dp0*int64((d-1)/2) + dp1*int64(d/2)
			dp0 = newDp0
			dp1 = newDp1
			prev = x
		}

		writer.WriteString(strconv.FormatInt(dp0+dp1, 10) + "\n")
	}
}