피보나치 표현

피보나치 수열은 다음과 같이 정의되는 정수 수열이며, 그 원소를 피보나치 수라고 부른다.

• $F_0 = 0$, $F_1 = 1$, 그리고 $n > 1$일 때 $F_n = F_{n-2} + F_{n-1}$

수열의 앞부분은 $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$ 이다.

Byteasar는 어떤 정수를 여러 피보나치 수의 합과 차로 나타내는 방법을 연구하고 있다. 지금 그가 알고 싶은 것은 주어진 양의 정수 $k$에 대한 최소 표현, 즉 사용하는 피보나치 수의 개수가 가장 적은 표현이다. 같은 피보나치 수를 여러 번 사용해도 된다. 예를 들어 $10$, $19$, $17$, $1070$은 각각 최소 $2$, $2$, $3$, $4$개의 피보나치 수로 다음과 같이 나타낼 수 있다.

• $10 = 5 + 5$
• $19 = 21 - 2$
• $17 = 13 + 5 - 1$
• $1070 = 987 + 89 - 5 - 1$

양의 정수 $k$가 주어질 때, $k$를 피보나치 수들의 합과 차로 나타내는 데 필요한 피보나치 수의 최소 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 질의의 개수를 나타내는 양의 정수 $p$ ($1 \le p \le 10$)가 주어진다. 이어지는 $p$개의 줄에는 각각 하나의 양의 정수 $k$ ($1 \le k \le 4 \cdot 10^{17}$)가 주어진다.

각 질의에 대해, $k$를 피보나치 수들의 합과 차로 나타내는 데 필요한 피보나치 수의 최소 개수를 한 줄에 하나씩 출력한다.