November Rain

Yeah, that's true. Nothing lasts forever, even a programming contest (5 hours pass so fast!). So, hurry up!

There's a path of $n$ meters long in between your Hall (Residence) and your Department (Academic Building). After last November Rain, the path has been flooded. Now, you have to repair the path by using bricks of size 1 meter long.

To repair the path what you will do is put the bricks one after another in a straight line. As you are in a hurry, you have to put the bricks fast. As a result, you become careless and some holes (missing of consecutive bricks) are created. Don't worry, holes are allowed as you are good at long jump. But alas, you have limitations too. You can't jump more than $m$ meters. So, you have to be at least this careful so that no hole makes you jump more than your limit.

Figure 1. describes a path (A-K) of 10 meters long. Each of the black cells denotes a brick. So, there are 3 holes (C, F-G, J) are created in total. You can put bricks in this formation only if your jumping limit is at least 3 meters. That's because it will take at least 3 meters jump to cover F-G hole (jump from E to H) and at least 2 meters jumps for C and J holes. Otherwise, you will fall down, your dress will get wet and most probably your friends will make great fun of you. So, be careful again when you are putting bricks on the path.

Note that, sometimes if your jumping limit is so high ($m > 10$ for Figure 1.), you may jump from the Hall to the Department directly without putting any bricks to the path at all (depends upon your wish). All you have to care is not to fall down in the water.

As you are in a programming contest, this path repairing task is hard for you anyway. So, give this task to the Problem-setter and take his task instead. And his task is simple - “Just count the number of ways to repair the path.”

More formally, count the number of ways to repair a $n$ meters long path by using 1 meter sized bricks so that it won't have any holes of size $m$ or more meters.

Input

Input starts with an integer $T$ ($T \le 100$), denoting the number of test cases.

Each case contains two integer numbers $n$, $m$ ($1 \le n, m \le 50000$, $|n - m| \le 500$) denoting the length of the path and your jumping limit.

Output

For each case print the case number and number of ways modulo 1000000007 ($10^9 + 7$). Follow the samples for exact formatting.

Sample

Input	Output
2 4 2 2 3	Case #1: 8 Case #2: 4