题目描述

在数学上，斐波那契数列是以递归的方法来定义：
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个斐波那契摇摆数是第几个斐波那契数吧。

输入要求

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

输出要求

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

输入样例

2
0
2

输出样例

0
2

提示

来源

NBU OJ