Description:


有一堆石子共有 \(N\) 个。 \(A,B\) 两个人轮流拿, \(A\) 先拿。每次拿的数量最少1个,最多不超过对手上一次拿的数量的2倍( \(A\) 第1次拿时要求不能全拿走)。拿到最后1颗石子的人获胜。假设 \(A,B\) 都非常聪明,拿石子的过程中不会出现失误。给出 \(N\) ,问最后谁能赢得比赛。
例如 \(N = 3\)\(A\) 只能拿1颗或2颗,所以 \(B\) 可以拿到最后1颗石子。

Input:


\(1\) 行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 1000)
\(2 \sim T + 1\) 行:每行1个数 \(N\) 。( \(1\le N \le 10^9\) )

Output:


\(T\) 行,如果 \(A\) 获胜输出 \(A\) ,如果 \(B\) 获胜输出 \(B\)

Sample Input


Sample Output:


题解:


博弈题一般第一件事就是打个表找规律……

然后就可以发现B赢就是斐波那契数列。

然后就没了。