UVA1633 Dyslexic Gollum

> “光，太阳与月亮的光，他仍然畏惧并憎恨，且我想他永远都会如此；但他很狡猾。他发现自己可以躲避白昼与月光，在漆黑的夜晚以冷淡的眼神迅速而悄无声息地行进，捕捉那些小而惊恐或疏忽的生物。随着新的食物和新的空气，他变得更强壮、更大胆。他找到了通往密林的路，就像人们预料的那样。” > > ——Gandalf，描述 Gollum 从 Moria 冒险出发后的情形。

Gollum 已经在 Moria 的漫长黑暗中度过了半个世纪，他的眼睛已经适应了黑暗，而由于他对阅读和写作不感兴趣，他变得有点阅读困难。事实上，正如他讨厌月亮和太阳一样，他也讨厌包含长回文子串的字符串。 Gollum 有一个容忍度 $K$，这意味着他只能阅读不包含任何长度为 $K$ 或更长的回文子串的单词。给定 $N$ 和 $K$ 的值，返回 Gollum 能容忍阅读的长度为 $N$ 的 01 串的数量。

第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例包含一行，包含两个整数 $N$ 和 $K$。

对于每个测试用例，输出的答案对 $1{,}000{,}000{,}007$ 取模。

### 限制 - $1 \le T \le 100$。 - $1 \le N \le 400$。 - $1 \le K \le 10$。 ### 说明 / 样例解释 对于第一组测试用例，$01$ 和 $10$ 是合法的 01 串，而 $00$ 和 $11$ 不是。 对于第二组测试用例，$001, 011, 100, 110$ 是合法的 01 串。 对于第三组测试用例，所有长度为 $3$ 的 01 串均满足要求。