피보나치 곱

피보나치 수열은 다음과 같이 정의된다: $F_0 = 1$, $F_1 = 1$, $F_n = F_{n-2} + F_{n-1}$. 피보나치 수열은 $1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$로 시작한다.

자연수 $n$이 주어진다. $n$을 1보다 큰 피보나치 수의 곱으로 나타내는 방법의 수를 구하라.

첫 줄에 테스트 케이스의 개수 $t$가 주어진다 ($1 \le t \le 50$). 다음 $t$개 줄에는 각각 정수 $n$이 하나씩 주어진다 ($2 \le n \le 10^{18}$).

각 테스트 케이스에 대해 방법의 수를 한 줄에 하나씩 출력한다.

예시에서 2는 $2 = 2$로 한 가지 방법으로만 표현된다. 7은 피보나치 수의 곱으로 나타낼 수 없다. 8은 $8 = 2 \times 2 \times 2$와 $8 = 8$로 두 가지 방법으로 표현된다. 40은 $40 = 2 \times 2 \times 2 \times 5$와 $40 = 5 \times 8$로 두 가지 방법으로 표현된다.