又见斐波那契

小码哥最近学习了斐波那契数列，它是这样一个数列 $F_n = F_{n-1} + F_{n-2},(n > 2)$，$F_1=1,F_2=2$。

小码哥想知道对于给定一个数 $x$，它有多少种方法分割成若干个互不相同的斐波那契数字，使得 $x$ 为这些斐波那契数字的和。

比如当 $x=3$ 时，有 $3=F_3$ 和 $3=F_1+F_2$ 两种方法。

输入格式

第一行一个数 $T$，表示有 $T(1 \le T \le 10^5)$ 组数据； 每组数据仅输入一个数 $x(1 \le x \le 10^6)$，表示询问 $x$ 有多少方法能分割成若干个互不相同的斐波那契数的和。

输出格式

对每组数据输出一个数，即 $x$ 分割成两两不同的斐波那契数的和的方法数。

样例输入

5
2
3
4
5
6

样例输出

1
2
1
2
2

数据范围

• 对于30% 的数据，满足 $1 \le T \le 100$，$1 \le x \le 1000$；
• 对于60% 的数据，满足 $1 \le T \le 10^4$，$1 \le x \le 10^5$；
• 对于100% 的数据，满足 $1 \le T \le 10^5$，$1 \le x \le 10^6$。