icebound在得到神殿的宝藏之后，开了一家神秘的商店。你来到了商店，发现慷慨的icebound搞了 T次促销活动。在每 次促销活动中，icebound都会想出一个他喜欢的数字，如果你买的商品的总价刚好等于icebound喜欢的数字，那么你就 可以免费得到这些商品。
icebound的商店里一共有 15件商品，商品的价格和这家商店一样神秘，第一件商品的价格是 1元，第二件商品的价格 是 2元，设第 n件商品的价格为 w _n元，则： w _n = w _n−1 + w _n−2 (3 ≤ n ≤ 15)。
如果在某次活动中icebound喜欢的数字是 4，那么共有 4种购买方案：
1. 买4个 第一种商品
2. 买4个 第一种商品 和1个 第二种商品
3. 买2个 第二种商品
4. 买1个 第一种商品 和1个 第三种商品
请你算出共有多少种方案可以免费购物，方案数对 1000000009(10 ⁹ +9)取模。

第一行给出一个整数 T，表示icebound搞了 T次活动。
接下来的 T行每行给出一个正整数 x，表示在这次活动中icebound喜欢的数字。
(1 ≤ T ≤ 3000, 1 ≤ x ≤ 3000)

输出 T行，每行输出一个正整数。
第 i行的正整数表示在第 i次活动中免费购物的方案数，方案数对 1000000009(10 ⁹ +9)取模。

2018CCPC河北省赛