描述

有些誓言说出来会很痛苦，比如说：“爱你是我最重要的事情，如果这件事情都做不了，我的人生就暗淡无光了”。

不过，我给予木姑娘的誓言，却不只是这么简单。

我有必要对于生命中最重要的k件事情给予评估，对于每一件事情的评估值分别是一个非负整数 ai。

不可能对于什么事情都给予很高的期望，所以 a[1]+a[2]+a[3]+...+a[k]=n 是一个限制标准。

最关键的事情是，对于相邻的两件事情，满足 a[i] and a[i+1] = a[i+1]。

这样的评估无疑是一种人生的规划，而人生的规划应该会有很多吧。

格式

输入格式

第一行给定整数 T，表示有多少组数据。1<=T<=5。

之后有T行，每行给定两个整数k和n，满足 3<=k<=100000，3<=n<=10000。

输出格式

对于每一组数据，输出一行表示对应的答案：有多少可行的人生规划，答案可能很大，所以只需要输出 mod 1000000009 后的余数。

样例1

样例输入1

2
3 2
4 2

样例输出1

2
2

限制

对于30％的数据，k<=5。
对于60％的数据，k<=1000。
对于100％的数据，k<=100000。