[丛雨]发现了一种未知的基因，这种基因的结构十分的奇怪。只由 $2$ 种元素构成，为了表示方便，我们用 $0$ ，$1$ 来表示这两种元素。这断基因中可以出现任意的 $0$，$1$ 组合，但是绝对不会出现两个连续的 $1$ (例如：$1000101010$ 是合法的，$10101011$ 是非法的)。 现在你要解决的是，给定一个基因长度 ，请输出有多少种不同的基因排列方法（长度为 $0$ 排方法为 $0$ ）。

输入格式（gene.in）

第一排一个数 $N$ 表示有 $N$ 个询问。以下 $N$ 排每排一个数 $K$ ，表示询问长度为 $K$ 的基因有多少种不同的组合方式。

输出格式（gene.out）

$N$ 排，每排对应一个询问。答案对 $12345$ 取余。

输入样例

2
1
2

输出样例

2
1
2

数据范围

对于 $30\%$ 的数据，保证 $n \le 1000$ 。 对于 $60\%$ 的数据，保证 $n \le 10000$ 。 对于 $100\%$ 的数据，保证 $0 \lt n \le 1000000, k \lt 100000$ 。