It's said that Aladdin had to solve seven mysteries beforegetting the Magical Lamp which summons a powerful Genie. Here we are concerned about the fifth mystery.

After defeating the Genie in 'Game of Bracelets', Aladdin moved forward and found a garden. There were n small Genies in the garden and they were all sad. Aladdin asked them about the lamp. But none of them was interested to answer the question. Aladdin decided to make them happy. Soon he noticed that height of every Genie is distinct but they were standing in a line randomly. Aladdin found a book there, and after reading the book, he discovered that the only way to make them happy was to make a line with the Genies such that k consecutive genies in the line could be found whose heights are inincreasing order. But the book also mentioned that if k+1 consecutive Genies found in the line whose heights are in increasing order then they would be sad again. So, Aladdin did make them happy, and they showed the path to Aladdin and he moved forward.

Now you are given n and k, your task is tofind in how many ways Aladdin could make them happy.

Input starts with an integer T (≤ 1275), denoting the number of test cases.

Each case starts with a line containing two integers: n and k (1 ≤ k ≤ n ≤ 50).

For each case, print the case number and the number of ways Aladdin could make them happy. As the result can be big; print the result modulo 1000000007 (10⁹ + 7).