本题由南山易准原创！在此感谢！
我们发现了一种未知的基因,这种基因的结构十分的奇怪.只由2种元素构成,为了表示方便,我们用0,1来表示这两种元素.这断基因中可以出现任意的0,1组合.但是绝对不会出现两个连续的1.

现在你要解决的是,给定一个基因长度 ,请输出有多少种不同的基因排列方法.
输入(例如:1000101010是合法的,10101011是非法的)
第一排一个数N 表示有N个询问;$0 \lt n \leq 1000000 $;
以下N排每排一个数K,表示询问长度为K的基因有多少种不同的组合方式.每个询问小于100000

输出:

N排 每排对应一个询问。

温馨提示：我知道大家讨厌万恶的高精度，因此你只用输出答案对12345取余；

样例： 输入

2
1
2
输出
2
3
样例解释 长度为1时有两种排列方法:0,1
长度为2时有三种排列方法:00,10,01