Description

小明在每天都在打卡签到。他发现前两天打卡都获得了1点经验值，从第三天开始，每天获得的经验值是昨天的经验值加上前天的经验值。他把一天签到可能获得的经验值数称为签到数。现在小明获得了一些神秘数字，他想知道，对于每个数字，将其表示为大于 1的签到数的乘积的方式数量，两个方式不相同当且仅当乘数由小到大排列后不相同。

Format

Input

第一行一个整数T，表示后面有T个数的询问。

接下来T行每行一个整数N，代表询问的数字。

Output

T行每行一个整数表示对应询问的答案。

Samples

5

2

7

8

40

64

1

0

2

2

3