Problem Description

Given n, k, calculate the number of different (unordered) partitions of n such that no part is repeated k or more times.

Input

First line, number of test cases, T.
Following are T lines. Each line contains two numbers, n and k.

1<=n,k,T<=10⁵

Output

T lines, each line contains answer to the responding test case.
Since the numbers can be very large, you should output them modulo 10⁹+7.

4
4 2
4 3
4 4
4 5

2
4
4
5