def solution(N, K):
    MOD = 10**9 + 7
 
    # Initialize DP table
    dp = [[0] * 2 for _ in range(N + 1)]
 
    # Base cases
    dp[0][0] = 1
 
    for i in range(1, N + 1):
        # Color the object with color 0
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD
 
        # Color the object with color 1
        dp[i][1] = dp[i - 1][0] # Always color the object with color 1 if possible
 
        # If distance between previous object colored with 1 and current object <= K
        if i >= K + 1:
            dp[i][1] = (dp[i][1] + dp[i - K - 1][1]) % MOD
 
    # Calculate total ways
    total_ways = (dp[N][0] + dp[N][1]) % MOD
 
    return total_ways
 
# Taking input from the user
T = int(input())
 
for _ in range(T):
    N, K = map(int, input().split())
    print(solution(N, K))
 

ZGVmIHNvbHV0aW9uKE4sIEspOgogICAgTU9EID0gMTAqKjkgKyA3CiAgICAKICAgICMgSW5pdGlhbGl6ZSBEUCB0YWJsZQogICAgZHAgPSBbWzBdICogMiBmb3IgXyBpbiByYW5nZShOICsgMSldCiAgICAKICAgICMgQmFzZSBjYXNlcwogICAgZHBbMF1bMF0gPSAxCiAgICAKICAgIGZvciBpIGluIHJhbmdlKDEsIE4gKyAxKToKICAgICAgICAjIENvbG9yIHRoZSBvYmplY3Qgd2l0aCBjb2xvciAwCiAgICAgICAgZHBbaV1bMF0gPSAoZHBbaSAtIDFdWzBdICsgZHBbaSAtIDFdWzFdKSAlIE1PRAogICAgICAgIAogICAgICAgICMgQ29sb3IgdGhlIG9iamVjdCB3aXRoIGNvbG9yIDEKICAgICAgICBkcFtpXVsxXSA9IGRwW2kgLSAxXVswXSAjIEFsd2F5cyBjb2xvciB0aGUgb2JqZWN0IHdpdGggY29sb3IgMSBpZiBwb3NzaWJsZQogICAgICAgIAogICAgICAgICMgSWYgZGlzdGFuY2UgYmV0d2VlbiBwcmV2aW91cyBvYmplY3QgY29sb3JlZCB3aXRoIDEgYW5kIGN1cnJlbnQgb2JqZWN0IDw9IEsKICAgICAgICBpZiBpID49IEsgKyAxOgogICAgICAgICAgICBkcFtpXVsxXSA9IChkcFtpXVsxXSArIGRwW2kgLSBLIC0gMV1bMV0pICUgTU9ECiAgICAKICAgICMgQ2FsY3VsYXRlIHRvdGFsIHdheXMKICAgIHRvdGFsX3dheXMgPSAoZHBbTl1bMF0gKyBkcFtOXVsxXSkgJSBNT0QKICAgIAogICAgcmV0dXJuIHRvdGFsX3dheXMKCiMgVGFraW5nIGlucHV0IGZyb20gdGhlIHVzZXIKVCA9IGludChpbnB1dCgpKQoKZm9yIF8gaW4gcmFuZ2UoVCk6CiAgICBOLCBLID0gbWFwKGludCwgaW5wdXQoKS5zcGxpdCgpKQogICAgcHJpbnQoc29sdXRpb24oTiwgSykpCg==

MQo1IDI=

1
5 2