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)取模。