题目描述

大家都知道，兔子数列是满足如下性质的一个数列：f(1) = 1 ，f(2) = 1 ，f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)。兔子数指该数列中的数，现在给定一个自然数n，求出将其表示为大于1的兔子数的乘积的方式数量。

输入格式

第一行一个数t，表示数据组数。 接下来t行，每行输入一个数m。（1 <= t <= 50，2 <= m <= 10^9）

输出格式

对于每组测试数据，输出一个数表示答案。

样例

input

5
2
7
8
40
64

output

1
0
2
2
3

样例解释

2 = 2
7 无法被表示为兔子数乘积
8 = 8 = 2×2×2
40 = 5×8 = 5×2×2×2
64 = 8×8 = 2×2×2×8 = 2×2×2×2×2×2