Description

在数学上，斐波那契数列是以递归的方法来定义：
f(0)=0
f(1)=1
f(n)=f(n-1)+f(n-2)

用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契系数就由之前的两数相加。首几个斐波那契数是
 
0,1,1,2,3,5,8.....
以上是斐波那契数列在维基百科上的定义
那什么是斐波那契摇摆数列呢，定义如下
f(0)=0
f(1)=1
f(n)=f(n-1)-f(n-2) n 为偶数
f(n)=f(n-1)+f(n-2) n 为奇数
ok，那请计算第n个斐波那契摇摆数是第几个斐波那契数吧。

Input

输入一个组数T（T < = 1000）
每组输入一个N (0 < = N < =  100,000)

Output

每组输出一个数，表示对应的是第几个斐波那契数，如果可能对应多个斐波那契数，则输出最大的序号。

Sample Input

2
0
2

Sample Output

0
2

HINT

Source

NBU OJ