Description

天地合，乃敢不君绝？

我们发现求出斐波那契数列在某种意义下可以作为解决一些有意义问题的方法，特别是在模5意义下的某种组合，或许可以破解敌方的密码系统。

出题人太懒了，对于算斐波那契数列这种难事，丌能找到简 便方法，因此他就懒得丌想做了（即使想做可能要买上一条1PB的内存条）。

他找到了善于思考、 用计算机快速解 决问题的你！你能帮帮他吗？

斐波那契数列的定义为 F(n)=F(n-1)+F(n-2)。

Format

Input

现有Q个询问， 每个询问都给出一个Qi。 对于每个询问 请你求出并输出斐波那契数列在模 5 意义下的第Qi项，每个询问的输出占一行。 Q<=10^6 Qi<=2*10^9 请留意本题数据范围。 本题共有25个测试点。

Output

如题

Samples

9
1 2 3 4 5 6 7 8 9

1 
1 
2 
3 
0 
3 
3
1 
4