数学课又要开始了。你迫不及待地想告诉 Nozomi 那个名为 “Knight Garden” 的游戏，而她则回赠了你一个名为 “Fibonacci of Fibonacci” 的谜题。
我们都对斐波那契数列非常熟悉，它可以通过以下递推关系定义：
$$F_0 = 0$$ $$F_1 = 1$$ $$F_n = F_{n-1} + F_{n-2}$$
由于计算 $F_n \bmod 20160519$ 对你来说太无聊了，她让你计算 $F_{F_n} \bmod 20160519$。
输入格式
第一行包含一个整数 $T$。
接下来的 $T$ 行，每行在单行中包含一个整数 $n$。
- $1 \le T \le 10000$
- $1 \le n \le 10^9$
输出格式
对于每个测试用例，在单行中输出一个整数 $F_{F_n} \bmod 20160519$。
样例
输入样例 1
2 5 6
输出样例 1
5 21